Discrete Mathematics

# Inleidende begrippen in discrete wiskunde Dit onderwerp legt de fundamentele concepten van discrete wiskunde uit, met de nadruk op logica, verzamelingenleer, kwantoren, en een introductie tot relaties en functies, ter voorbereiding op verdere wiskundige analyses [6](#page=6). ### 1.1 Logica Logica vormt de basis voor wiskundige redeneringen en wordt bestudeerd in de discipline genaamd logica. Hierbij wordt de taal en notatie van de predikatenlogica gehanteerd [6](#page=6). * **Propositie:** Een bewering die waar of onwaar is [6](#page=6). * **Conjunctie:** `p ∧ q` (p en q) [6](#page=6). * **Disjunctie:** `p ∨ q` (p of q) [6](#page=6). * **Implicatie:** `p ⇒ q` (Als p dan q) [6](#page=6). * Voorbeeld: "x is deelbaar door 10 ⇒ x is even" [6](#page=6). * **Equivalentie:** `p ⇔ q` (p is equivalent met q) is equivalent aan `(p ⇒ q) ∧ (q ⇒ p)` [6](#page=6). * Voorbeeld: "n² even ⇔ n even" [6](#page=6). * **Negatie:** `¬p` [6](#page=6). * Voorbeeld: "Het regent niet." [6](#page=6). > **Tip:** De negatie van een implicatie `¬(p ⇒ q)` is equivalent aan `p ∧ ¬q`. De contrapositie van een implicatie `p ⇒ q` is equivalent aan `¬q ⇒ ¬p`. Het bewijs van de implicatie is vaak gemakkelijker te voeren via de contrapositie [7](#page=7). ### 1.2 Verzamelingen Een verzameling is een fundamenteel wiskundig begrip dat objecten met dezelfde kenmerken groepeert. Een object dat tot een verzameling behoort, heet een element. Verzamelingen worden meestal aangeduid met hoofdletters [7](#page=7). Veelgebruikte verzamelingen met speciale symbolen: * `N = {0, 1, 2,... }`: de natuurlijke getallen [7](#page=7). * `Z = {..., −3, −2, −1, 0, 1, 2,... }`: de gehele getallen [7](#page=7). * `Q = {a/b | a, b ∈ Z ∧ b ≠ 0 }`: de rationale getallen [7](#page=7). * `R`: de reële getallen [7](#page=7). * `C = {a + bi | a, b ∈ R}`: de complexe getallen [7](#page=7). Verzamelingen kunnen worden gedefinieerd door de elementen op te sommen tussen accolades `{}` of door een algemene beschrijving van de elementen te geven. Het symbool `∈` betekent "is element van" of "behoort tot", terwijl `∉` betekent "is geen element van" [7](#page=7). * `R₀ = {x ∈ R | x ≠ 0}` [7](#page=7). * `R⁺ = {x ∈ R | x ≥ 0}` [7](#page=7). * `R⁺₀ = {x ∈ R | x > 0}` [7](#page=7). Voor eindige verzamelingen `A` noteren we het aantal elementen als `|A|` of `# A`. De lege verzameling `∅` bevat geen elementen [8](#page=8). ### 1.3 Kwantoren Kwantoren worden gebruikt om uitspraken te doen over alle of sommige elementen van een verzameling [8](#page=8). * **Universele kwantor:** `∀` (voor alle) [8](#page=8). * Voorbeeld: `∀x ∈ R: x² ≥ 0`. Het dubbelpunt `:` kan gelezen worden als "geldt" in een logische uitspraak [8](#page=8). * **Existentiële kwantor:** `∃` (er bestaat) [8](#page=8). * Voorbeeld: `∃x ∈ R: x² = x` [8](#page=8). * **Unieke existentiële kwantor:** `∃!` (er bestaat precies één) [8](#page=8). * Voorbeeld: `∃! x ∈ R⁺₀: x² = x` [8](#page=8). #### 1.3.1 Meerdere kwantoren en negaties De volgorde van kwantoren is cruciaal en beïnvloedt de betekenis van een uitspraak [8](#page=8). * `∀x ∈ R: ∃y ∈ R⁺: x² = y` is waar [8](#page=8). * `∃y ∈ R⁺: ∀x ∈ R: x² = y` is onwaar [8](#page=8). De variabele namen die gebruikt worden bij kwantoren hebben geen belang voor de betekenis van de uitspraak [8](#page=8). **Negaties van uitspraken met kwantoren:** * De negatie van `∀x ∈ X: p(x)` is `∃x ∈ X: ¬p(x)` [8](#page=8). * De negatie van `∃x ∈ X: p(x)` is `∀x ∈ X: ¬p(x)` [8](#page=8). > **Tip:** Negaties van uitspraken met kwantoren zijn erg belangrijk, bijvoorbeeld bij het bewijs door contrapositie [8](#page=8). * Voorbeeld: De negatie van `∀ε ∈ R⁺₀: ∃δ ∈ R⁺₀: ∀x ∈ X: (|x − a| < δ) ⇒ (|f(x) − f(a)| < ε)` is `∃ε ∈ R⁺₀: ∀δ ∈ R⁺₀: ∃x ∈ X: (|x − a| < δ) ∧ (|f(x) − f(a)| ≥ ε)` [9](#page=9). ### 1.4 Deelverzamelingen en gelijke verzamelingen Als elk element van een verzameling `A` ook tot een verzameling `B` behoort, is `A` een deelverzameling van `B` [9](#page=9). * **Notatie:** `A ⊂ B ⇔ ∀ a ∈ A: a ∈ B` [9](#page=9). * Alternatieve notatie: `B ⊃ A` [9](#page=9). * Elke verzameling is een deelverzameling van zichzelf: `B ⊂ B` [9](#page=9). * De lege verzameling is een deelverzameling van elke verzameling: `∅ ⊂ B` [9](#page=9). * Een deelverzameling `A` van `B` waarbij `A ≠ B` heet een **echte deelverzameling** [9](#page=9). * Voorbeelden: * `{1, 2, 3} ⊂ N ⊂ Z ⊂ Q ⊂ R ⊂ C` [9](#page=9). * `Z ̸⊂ R⁺` [9](#page=9). Twee verzamelingen `A` en `B` zijn **gelijk** (`A = B`) als en slechts als `A ⊂ B` en `B ⊂ A`. Ze zijn ongelijk (`A ≠ B`) als er een element in `A` zit dat niet in `B` zit, óf als er een element in `B` zit dat niet in `A` zit [9](#page=9). De verzameling van alle deelverzamelingen van een gegeven verzameling `X` wordt genoteerd als `P(X)` [9](#page=9). * `P(X) = {S verzameling | S ⊂ X}` [9](#page=9). ### 1.5 Bewerkingen met verzamelingen * **Doorsnede:** De doorsnede van `A` en `B` is de verzameling `A ∩ B = {x ∈ A | x ∈ B}` [9](#page=9). * Twee verzamelingen `A` en `B` zijn **disjunct** als `A ∩ B = ∅` [9](#page=9). * **Unie:** De unie van `A` en `B` is `A ∪ B = {x | (x ∈ A) ∨ (x ∈ B)}` [9](#page=9). * **Verschil:** Het verschil van `A` en `B` is `A \ B = {x | (x ∈ A) ∧ (x ∉ B)}` [9](#page=9). * Voorbeeld: Stel `A = {1, 2, 3}` en `B = {2, 3, 4, 5}`. Dan geldt: * `A ∩ B = {2, 3}` [10](#page=10). * `A ∪ B = {1, 2, 3, 4, 5}` [10](#page=10). * `A \ B = {1}` [10](#page=10). * `B \ A = {4, 5}` [10](#page=10). Als `A ⊂ B`, dan heet `B \ A` het **complement van A ten opzichte van B**. Als een theorie zich afspeelt binnen een universum `U`, worden complementen berekend ten opzichte van `U`. Voor `A ⊂ U` noteert men `Aᶜ`, `Ā` of `∁A` voor `U \ A` [10](#page=10). #### 1.5.1 Oneindige unies en doorsneden Voor een indexverzameling `I` en verzamelingen `Aᵢ` voor elke `i ∈ I`, definieert men: * **Doorsnede:** `⋂_{i∈I} Aᵢ = {x | ∀i ∈ I: x ∈ Aᵢ}` [10](#page=10). * **Unie:** `⋃_{i∈I} Aᵢ = {x | ∃i ∈ I: x ∈ Aᵢ}` [10](#page=10). * Voorbeeld: Stel `I = {3, 4, 5, 6, 7}` en `Aᵢ = {1, 2,..., i}`. Dan is `⋃_{i∈I} Aᵢ = A₇` en `⋂_{i∈I} Aᵢ = A₃` [10](#page=10). #### 1.5.2 Cartesisch product Het cartesisch product van twee verzamelingen `A` en `B` is de verzameling `A × B = {(a, b) | a ∈ A, b ∈ B}`. De elementen zijn geordende koppels [10](#page=10) [11](#page=11). * `(a, b) = (c, d) ⇔ (a = c) ∧ (b = d)` [11](#page=11). * Als `A` en `B` eindig zijn, geldt `|A × B| = |A| ⋅ |B|` [11](#page=11). * `A × A` wordt genoteerd als `A²` [11](#page=11). ### 1.6 Relaties Een relatie van een verzameling `A` naar een verzameling `B` is een deelverzameling `R` van het cartesisch product `A × B` [11](#page=11). * Als `(a, b) ∈ R`, schrijven we `aRb` [11](#page=11). * Voorbeeld: Beschouw de verzameling `A = {1, 2, 3, 4}` en de relatie "is kleiner dan of gelijk aan" (`≤`). Dan is `R = {(a, b) ∈ A × A | a ≤ b}` [11](#page=11). De **inverse relatie** `R⁻¹` van `R` is gedefinieerd als `R⁻¹:= {(b, a) | (a, b) ∈ R}`. Dit is een relatie van `B` naar `A` [11](#page=11). ### 1.7 Functies Een functie van een verzameling `A` naar een verzameling `B` is een relatie van `A` naar `B` waarbij elk element van `A` precies één keer voorkomt als eerste component van een koppel in de relatie [12](#page=12). * `A` heet het **domein** van de functie. * `B` heet het **codomein** van de functie. * Notatie: `f : A → B`. * Als `(a, b) ∈ f`, noteren we `f(a) = b`. * `b` heet het **beeld** van `a` door `f`. * `a` heet een **origineel** van `b` voor `f`. * Notatie voor het afbeelden: `a ↦→ b` [12](#page=12). Het **functievoorschrift** geeft de regel om het beeld van een element te berekenen [12](#page=12). * Volledige notatie: `f: A → B: a ↦−→ f(a)` [12](#page=12). > **Tip:** Een functie wordt volledig gedefinieerd door domein, codomein en functievoorschrift; alle drie zijn even belangrijk [12](#page=12). #### 1.7.1 Beeld en invers beeld Voor een functie `f : A → B` en `S ⊂ A`: * **Beeld van S:** `f(S):= {f(s) | s ∈ S}`. Dit is een deelverzameling van `B` [12](#page=12). * **Beeld van f (Im f):** De verzameling `f(A)`, het beeld van het hele domein van `f`. Dit is een deel van het codomein [13](#page=13). * Voorbeeld: `f: R → R: x ↦→ x²`. Dan is `f([−1, 2]) = ` en `Im f = R⁺` [13](#page=13) [4](#page=4). Voor een functie `f : A → B` en `T ⊂ B`: * **Invers beeld van T:** `f⁻¹(T):= {a ∈ A | f(a) ∈ T}`. Deze notatie impliceert niet dat er een inverse functie bestaat [13](#page=13). * Als `T` een singleton `{b}` is, schrijven we `f⁻¹(b)` [13](#page=13). * Voorbeeld: Met `f(x) = x²` hebben we `f⁻¹ = {−2, 2}`, `f⁻¹(−1) = ∅` en `f⁻¹(f( )) = [−1, 1]` [13](#page=13) [1](#page=1) [4](#page=4). #### 1.7.2 Geïnduceerde functies, restrictie en corestrictie * **Geïnduceerde functies:** Functies die afgeleid worden uit een bestaande functie `f`, bijvoorbeeld op `A × A` of op de machtsverzameling `P(A)` [13](#page=13). * **Restrictie (beperking):** De functie `f` bekeken op een deelverzameling `X` van `A`. Genoteerd als `f|X: X → B: x ↦→ f(x)` [14](#page=14). * **Corestrictie:** Het beperken van het codomein van `f` tot een deelverzameling `Y ⊂ B` zodanig dat `∀a ∈ A: f(a) ∈ Y`. Genoteerd als `f|Y: A → Y: x ↦→ f(x)` [14](#page=14). ### 1.8 Injecties en surjecties * **Injectieve functie (één-op-één):** Elk element van het codomein heeft hoogstens één origineel [14](#page=14). * Formeel: `f: A → B` is injectief ⇔ `∀a, b ∈ A: (f(a) = f(b)) ⇒ (a = b)` [14](#page=14). * Voorbeeld: `f: R → R: x ↦→ x²` is niet injectief (`1² = (−1)²`). `g: R⁺ → R: x ↦→ x²` is wel injectief [14](#page=14). * **Surjectieve functie (op):** Elk element van het codomein heeft minstens één origineel [14](#page=14). * Formeel: `f: A → B` is surjectief ⇔ `Im f = B` ⇔ `∀b ∈ B: ∃a ∈ A: f(a) = b` [14](#page=14). * Voorbeeld: `g: R⁺ → R: x ↦→ x²` is niet surjectief. `g|R⁺` (waarbij het codomein ook `R⁺` is) is wel surjectief [14](#page=14). Een functie die zowel injectief als surjectief is, heet **bijectief** [15](#page=15). * Formeel: `f` is bijectief ⇔ `∀b ∈ B: ∃! a ∈ A: f(a) = b` [15](#page=15). Een bijectie van een verzameling naar zichzelf heet een **permutatie**. De **identieke permutatie** `1ₓ: X → X: x ↦→ x` beeldt elk element op zichzelf af [15](#page=15). ### 1.9 De samenstelling van functies Gegeven twee functies `f: A → B` en `g: B → C`, wordt de **samenstelling** `g ◦ f: A → C` gedefinieerd als `(g ◦ f)(a) = g(f(a))`. Eerst wordt `f` toegepast, daarna `g` [15](#page=15). * Voorbeeld: `f(x) = x − 1` en `g(x) = x²`. * `g ◦ f: x ↦→ (x − 1)²` [15](#page=15). * `f ◦ g: x ↦→ x² − 1` [15](#page=15). > **Tip:** De volgorde van samenstelling is belangrijk; in het algemeen geldt `f ◦ g ≠ g ◦ f` [16](#page=16). De samenstelling van functies is **associatief**: `h ◦ (g ◦ f) = (h ◦ g) ◦ f` [16](#page=16). ### 1.10 Inverse functies Een functie `g: B → A` is een **invers** van `f: A → B` als `f ◦ g = 1_B` en `g ◦ f = 1_A`. Een functie is **inverteerbaar** als ze een inverse heeft [16](#page=16). * **Stelling:** Enkel bijectieve functies hebben een invers [17](#page=17). * **Eigenschap:** Een functie heeft hoogstens één invers. De inverse functie wordt genoteerd als `f⁻¹` [17](#page=17). > **Let op:** `f⁻¹` als inverse functie is anders dan `f⁻¹(T)` voor het invers beeld van een verzameling `T`. * Voorbeeld: `h: R⁺ → R⁺: x ↦→ x²` is bijectief. Haar inverse is `h⁻¹: R⁺ → R⁺: x ↦→ √x` [17](#page=17). --- # Eenvoudige principes van discrete wiskunde en teltechnieken Dit hoofdstuk introduceert fundamentele principes van discrete wiskunde, waaronder het duiventilprincipe en diverse teltechnieken zoals productregels, permutaties, combinaties en het binomium van Newton. ## 2.1 De duiventil Het duiventilprincipe stelt dat wanneer $n$ identieke objecten worden verdeeld over $k$ dozen, en $n > k$, er minstens één doos zal zijn met meer dan één object [23](#page=23). **Stelling 2 (Principe van de duiventil)**: Als we $n$ identieke objecten verdelen over $k$ dozen met $n > k$, dan is er minstens één doos met minstens twee objecten [23](#page=23). **Bewijs (uit het ongerijmde)**: Veronderstel dat er in elke doos hoogstens één object is. Als $m$ het aantal lege dozen is, dan zijn er $k-m$ dozen met elk precies één object. De totale objecten zijn dan $n = k-m$. Aangezien $m \ge 0$, geldt $n \le k$. Dit is een tegenspraak met de aanname $n > k$ [23](#page=23). **Gevolg 1**: In de eerste 2013 elementen van de rij 7, 77, 777,... zit minstens één veelvoud van 2013. Dit wordt bewezen door de resten van deze getallen bij deling door 2013 te beschouwen. Er zijn 2013 getallen en 2012 mogelijke niet-nul resten. Volgens het duiventilprincipe moeten minstens twee getallen dezelfde rest hebben, wat impliceert dat hun verschil deelbaar is door 2013 [23](#page=23) [24](#page=24). **Veralgemeende duiventil**: Als $n$ identieke objecten worden verdeeld over $k$ dozen, dan is er minstens één doos met minstens $\lceil \frac{n}{k} \rceil$ objecten [24](#page=24). **Voorbeeld**: In een groep van 100 mensen zijn er minstens 9 die hun verjaardag vieren in dezelfde maand [24](#page=24). **Voorbeeld (Ramsey theorie)**: In een groep van 6 mensen zijn elke twee individuen ofwel vrienden ofwel vijanden. Er zijn zeker drie mensen die onderling ofwel allemaal vrienden zijn ofwel allemaal vijanden [24](#page=24). **Notatie**: * $\lceil x \rceil$: kleinste gehele getal $\ge x$ [24](#page=24). * $\lfloor x \rfloor$: grootste gehele getal $\le x$ [24](#page=24). ## 2.2 Eenvoudige teltechnieken Twee eindige verzamelingen $A$ en $B$ hebben evenveel elementen indien er een bijectie tussen hen bestaat [25](#page=25). ### 2.2.1 Tellen **Definitie 4**: Een verzameling $A$ heeft $n \in \mathbb{N}$ elementen indien er een bijectie bestaat van $[n = \{1, 2, \ldots, n\}$ naar $A$. Deze bijectie bepaalt een ordening of nummering van $A$ [26](#page=26). **Stelling 3**: Voor elke eindige verzameling $X$ geldt $|P(X)| = 2^{|X|}$, waarbij $P(X)$ de machtsverzameling van $X$ is. Dit betekent dat een verzameling met $n$ elementen $2^n$ deelverzamelingen heeft [26](#page=26). ### 2.2.2 Somprincipe **Stelling 4 (Somprincipe)**: Zijn $A_1, A_2, \ldots, A_k$ twee aan twee disjuncte eindige verzamelingen. Dan geldt: $$|A_1 \cup A_2 \cup \cdots \cup A_k| = |A_1| + |A_2| + \cdots + |A_k|$$ [26](#page=26). ## 2.3 Teltechnieken met producten ### 2.3.1 Dubbeltellen **Stelling 5 (Principe van de dubbeltelling)**: Zij $A$ en $B$ twee (eindige) verzamelingen. Zij $S \subseteq A \times B$. Stel voor elke $a \in A$: $k_a = |\{(a, b) \mid b \in B \text{ en } (a, b) \in S\}|$ en voor elke $b \in B$: $r_b = |\{(a, b) \mid a \in A \text{ en } (a, b) \in S\}|$. Dan geldt: $$\sum_{a \in A} k_a = |S| = \sum_{b \in B} r_b$$ [27](#page=27). **Gevolg 2**: Als alle $k_a$ gelijk zijn aan een constante $k$ en alle $r_b$ gelijk zijn aan een constante $r$, dan geldt $k|A| = r|B|$ [27](#page=27). **Toepassing**: Een dodecaëder heeft 30 ribben, omdat er 12 zijvlakken met elk 5 ribben zijn en elke ribbe op 2 zijvlakken ligt. We tellen de koppels (ribbe, zijvlak) op twee manieren: `#ribben * 2 = 12 * 5` [28](#page=28). ### 2.3.2 Woorden Een woord van lengte $m$ over een alfabet $Y$ is een $m$-tupel van elementen uit $Y$. Er is een één-op-één correspondentie tussen $m$-tupels in $Y^m$ en functies van $[m]$ naar $Y$ [28](#page=28). **Stelling 6**: Zijn $X, Y$ eindige verzamelingen, met $|X|=m$ en $|Y|=n$. Dan geldt: $$\text{#{functies } f : X \to Y} = n^m$$ [28](#page=28). **Voorbeeld**: Het aantal woorden van lengte 3 in ons alfabet (26 letters) is $26^3$ [28](#page=28). ### 2.3.3 Injecties tellen **Stelling 7**: Het aantal geordende keuzes van $m$ objecten uit $n$ zonder herhaling is $n(n-1)(n-2)\cdots(n-m+1)$ [29](#page=29). **Notatie**: De faculteit van een natuurlijk getal $n \in \mathbb{N}$ is $n! = n \cdot (n-1) \cdots 3 \cdot 2 \cdot 1$. Per definitie stellen we $0! = 1$ [29](#page=29). Het aantal keuzes in stelling 7 kan worden genoteerd als $\frac{n!}{(n-m)!}$. Dit aantal is ook bekend als het aantal $m$-permutaties van $n$ elementen, genoteerd als $P(n, m)$ of $n P m$ [29](#page=29). ### 2.3.4 Bijecties tellen Als in stelling 7 geldt dat $n=m$, dan kunnen we op $n!$ verschillende manieren $n$ objecten kiezen waarbij de volgorde van belang is. Dit is het aantal bijecties van $[n]$ naar een verzameling $Y$ met $|Y|=n$ [29](#page=29). Een bijectie $f: Y \to Y$ van een verzameling naar zichzelf wordt een permutatie genoemd. Een permutatie is een (her)ordening van $Y$ [29](#page=29). ### 2.3.5 Deelverzamelingen tellen **Stelling 8**: Het aantal keuzes van $k$ elementen uit een verzameling van $n$ elementen, zonder volgorde en zonder herhaling, bedraagt: $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$ . Dit getal wordt genoteerd als $\binom{n}{k}$ en heet een binomiaalcoëfficiënt [30](#page=30). We merken op dat $\binom{n}{n-k} = \binom{n}{k}$ [30](#page=30). **Notatie**: De verzameling van alle $k$-deelverzamelingen van $A$ wordt genoteerd als $\binom{A}{k}$, zodat $|\binom{A}{k}| = \binom{|A|}{k}$ [30](#page=30). **Eigenschap 3 (Identiteit van Pascal)**: Zij $n, k \in \mathbb{N}_0$ met $k \le n$. Dan geldt: $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$ . Deze identiteit is de basis voor de driehoek van Pascal [31](#page=31). ### 2.3.6 Herhalingscombinaties Het aantal manieren om $k$ objecten te kiezen uit $n$ types, met terugleggen en zonder rekening te houden met de volgorde, is gelijk aan $\binom{n+k-1}{k}$ [32](#page=32). **Eigenschap 4**: Voor $n \in \mathbb{N}$ geldt: $$\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \cdots + (-1)^n \binom{n}{n} = 0$$ [32](#page=32). ## 2.4 Het binomium van Newton **Stelling 9 (Binomium van Newton)**: Voor alle $a, b$ en $n \in \mathbb{N}$ geldt: $$(a + b)^n = \sum_{i=0}^{n} \binom{n}{i} a^{n-i}b^i$$ . De coëfficiënten $\binom{n}{i}$ worden binomiaalcoëfficiënten genoemd [33](#page=33). **Voorbeeld**: $(1 - x)^7 = 1 - 7x + 21x^2 - 35x^3 + 35x^4 - 21x^5 + 7x^6 - x^7$ [33](#page=33). **Stelling 10**: Voor alle $n \in \mathbb{N}$ geldt: $$\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$$ . Dit wordt bewezen door de coëfficiënt van $x^n$ in $(1+x)^n (1+x)^n = (1+x)^{2n}$ te vergelijken [33](#page=33) [34](#page=34). ## 2.5 Inclusie en exclusie Voor twee verzamelingen: $|A \cup B| = |A| + |B| - |A \cap B|$ [34](#page=34). Voor drie verzamelingen: $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ [34](#page=34). **Stelling 11 (Principe van inclusie en exclusie)**: Zijn $A_1, A_2, \ldots, A_n$ eindige verzamelingen. Dan hebben we: $$|\bigcup_{i=1}^{n} A_i| = \sum_{i} |A_i| - \sum_{i0$ betekent $k$ pijlen van $u$ naar $v$. Pijlen met hetzelfde begin- en eindpunt zijn parallel. Een multigraaf zonder parallelle pijlen is een graaf [84](#page=84). **Definitie 23.** Een pad in een ongerichte multigraaf $G$ is een **Eulerpad** als het elke boog van $G$ precies één maal bevat. Een gesloten Eulerpad is een **Eulercyclus**. Een multigraaf met een Eulercyclus heet een **Eulergraaf** [84](#page=84). **Stelling 30 (Euler, 1736).** Een ongerichte multigraaf $G$ zonder geïsoleerde toppen is een Eulergraaf als en slechts als $G$ samenhangend is en alle toppen van $G$ even graad hebben [85](#page=85). **Gevolg 9.** Een samenhangende ongerichte multigraaf $G$ heeft een Eulerpad dat niet gesloten is als en slechts als $G$ precies twee toppen van oneven graad heeft [86](#page=86). #### 4.4.2 Hamiltonpaden **Definitie 24.** Een **simpel pad** dat alle toppen van een multigraaf $G$ bevat heet een **Hamiltonpad**. Een **Hamiltoncyclus** is een gesloten Hamiltonpad. Een multigraaf met een Hamiltoncyclus heet een **Hamiltongraaf** [87](#page=87). **Lemma 4.** Als je $k$ toppen uit een Hamiltongraaf $G$ weglaat (samen met aangrenzende bogen), valt $G$ uiteen in hoogstens $k$ samenhangscomponenten [87](#page=87). **Stelling 31.** Als het verwijderen van $n$ toppen uit een graaf $G$ leidt tot $m > n$ samenhangscomponenten, dan is $G$ geen Hamiltongraaf [87](#page=87). **Stelling 32 (Dirac, 1952).** Een ongerichte simpele graaf $G$ met $n \ge 3$ toppen, waarbij elke top minstens graad $\frac{n}{2}$ heeft, heeft een Hamiltoncyclus [87](#page=87). #### 4.4.3 Gerichte grafen **Definitie 25.** Een gerichte (multi)graaf is een **gerichte Eulergraaf** indien er een gesloten gericht pad bestaat dat elke pijl precies één keer gebruikt [89](#page=89). **Stelling 33.** Een samenhangende gerichte (multi)graaf $G$ is een gerichte Eulergraaf als en slechts als $G$ sterk samenhangend en gebalanceerd is [89](#page=89). **Definitie 26.** Een **toernooi** is een gerichte simpele graaf die ontstaat door alle bogen van een complete graaf te oriënteren [90](#page=90). **Stelling 34.** Elk toernooi heeft een gericht Hamiltonpad [90](#page=90). **Stelling 35.** Een toernooi $T$ heeft een gericht Hamiltoncyclus als en slechts als $T$ sterk samenhangend is [90](#page=90). ### 4.5 Isomorfismen tussen grafen **Definitie 27.** Een afbeelding $f: V \rightarrow W$ tussen twee multigrafen $(V, \mu)$ en $(W, \phi)$ is een **morfisme** indien $\phi(f(u), f(v)) = \mu(u, v)$ voor alle $(u, v) \in V \times V$ [92](#page=92). **Definitie 28.** Twee multigrafen $(V, \mu)$ en $(W, \phi)$ zijn **isomorf** als er een bijectief morfisme $f: V \rightarrow W$ bestaat. Dit morfisme heet een isomorfisme. Voor ongerichte simpele grafen $G = (V, \sim_G)$ en $H = (W, \sim_H)$ is een isomorfisme een bijectie $f: V \rightarrow W$ zodanig dat $u \sim_G v \Leftrightarrow f(u) \sim_H f(v)$. Notatie: $G \cong H$ [92](#page=92). ### 4.6 Bomen en bossen **Definitie 29.** Een **boom** is een samenhangende ongerichte simpele graaf zonder cyclus [93](#page=93). **Stelling 36.** Een samenhangende simpele graaf $G$ is een boom als en slechts als hij minimaal samenhangend is (het weglaten van een boog maakt hem niet meer samenhangend) [93](#page=93). **Gevolg 10.** Een samenhangende ongerichte graaf is een boom als en slechts als elke twee toppen verbonden zijn door precies één pad [93](#page=93). **Definitie 30.** Een top van graad 1 in een boom heet een **blad** [94](#page=94). **Lemma 5.** Een boom op $n \ge 2$ toppen heeft minstens twee bladeren [94](#page=94). **Stelling 37.** Een boom met $n$ toppen heeft $n-1$ bogen [94](#page=94). **Definitie 31.** Een gerichte graaf $G$ is een **gerichte boom** als de geassocieerde ongerichte graaf een boom is. Een **gewortelde boom** is een gerichte boom met een unieke top met ingraad nul en alle andere toppen met ingraad één [94](#page=94). **Definitie 32.** Een **bos** is een ongerichte simpele graaf zonder cyclus. De samenhangscomponenten van een bos zijn bomen [95](#page=95). **Eigenschap 16.** Een bos $F$ met $n$ toppen en $k$ samenhangscomponenten heeft precies $n-k$ bogen [95](#page=95). **Definitie 33.** Een **genummerde (gelabelde) boom** is een boom met toppenverzameling $[n]$ voor $n \in \mathbb{N} \setminus \{0, 1\}$ [95](#page=95). **Stelling 38 (Cayley).** Het aantal genummerde bomen met $n$ toppen is $n^{n-2}$ [95](#page=95). **Gevolg 11.** Het aantal gewortelde genummerde bomen op $n$ toppen is $n^{n-1}$ [96](#page=96). **Gevolg 12.** Het aantal gewortelde genummerde bossen op $n$ toppen is $(n+1)^{n-1}$ [96](#page=96). #### 4.6.1 Opspannende bomen **Definitie 34.** Een **gewogen graaf** is een graaf samen met een gewichtsfunctie $w: E(G) \rightarrow \mathbb{R}^+$ die aan elke pijl een prijs of gewicht toekent [97](#page=97). **Gierigheidsalgoritme (Kruskal).** Om een opspannende boom $T$ van minimaal gewicht te vinden in een gewogen samenhangende ongerichte simpele graaf $(G, w)$: 1. Neem een boog met het kleinste gewicht om $T$ te starten. 2. Neem een boog met het kleinste gewicht in $G$ die nog niet tot $T$ behoort en geen cyclus creëert als hij aan $T$ wordt toegevoegd. 3. Ga naar tot $T$ een opspannende boom is [2](#page=2) [97](#page=97). **Stelling 39.** Het gierigheidsalgoritme vindt steeds een opspannende boom met minimaal gewicht [98](#page=98). Het **handelsreizigersprobleem** zoekt een Hamiltoncyclus met minimaal gewicht [98](#page=98). #### 4.6.2 Het tellen van opspannende bomen **Incidentiematrix ($B$)** van een gerichte multigraaf $G=(V,E)$ met $V=\{v_1, \dots, v_n\}$ en $E=\{b_1, \dots, b_m\}$ is de $n \times m$-matrix met: $b_{ij} = 1$ als $v_i$ het eindpunt is van $b_j$. $b_{ij} = -1$ als $v_i$ het beginpunt is van $b_j$. $b_{ij} = 0$ anders [99](#page=99). **Stelling 40 (Kirchhoff).** Het aantal opspannende bomen in een gerichte multigraaf $G$ zonder lussen is gelijk aan de determinant van een matrix $B_0$, waarbij $B_0$ de incidentiematrix $B$ is na verwijdering van een willekeurige rij. Dus: aantal opspannende bomen $= \det(B_0 B_0^\top)$ [99](#page=99). **Laplaciaanse matrix ($L_G$)** voor een ongerichte simpele graaf $G=(V,E)$ met $|V|=n$ is de $n \times n$-matrix met: $l_{ij} = \text{deg}(v_i)$ als $i=j$. $l_{ij} = -1$ als $i \neq j$ en $v_i \sim v_j$. $l_{ij} = 0$ anders [100](#page=100). **Stelling 41.** Het aantal opspannende bomen in een ongerichte simpele graaf is gelijk aan elke cofactor van $L_G$ [100](#page=100). * **Toepassing:** Het aantal opspannende bomen in een complete graaf $K_n$ is $n^{n-2}$ (Cayley's stelling) [100](#page=100). #### 4.6.3 Samenhang van een graaf bestuderen **Adjacentiematrix ($A_G$)** van een graaf $G$ met $n$ toppen is de $n \times n$-matrix waarbij $a_{ij}$ het aantal pijlen is van de $i$-de naar de $j$-de top . **Stelling 42.** Het element op plaats $(i,j)$ in $A_G^k$ geeft het aantal (gerichte) wandelingen van lengte $k$ van top $i$ naar top $j$ . **Stelling 43.** Een ongerichte multigraaf $G$ op $n$ toppen is samenhangend als en slechts als $(I_n + A_G)^{n-1}$ enkel strikt positieve elementen heeft . ### 4.7 Bipartiete grafen **Definitie 36.** Een multigraaf is **bipartiet** indien zijn toppenverzameling partitioneerbaar is in twee disjuncte verzamelingen $V_1$ en $V_2$ zodanig dat elke boog een top in $V_1$ en een top in $V_2$ verbindt. Dit kan gemodelleerd worden door de toppen met twee kleuren te kleuren zodat geen aangrenzende toppen dezelfde kleur hebben . **Stelling 44.** Een ongerichte multigraaf $G$ is bipartiet als en slechts als $G$ geen cyclus van oneven lengte bevat . **Stelling 45.** Een bipartiete ongerichte graaf $G$ met $n$ toppen heeft hoogstens $\lfloor n^2/4 \rfloor$ bogen . **Stelling 46.** Een ongerichte simpele graaf $H$ met $2m$ toppen ($m \ge 2$) en minstens $m^2 + 1$ bogen bevat een driehoeksgraaf ($K_3$) . **Stelling 47 (Turán).** Een ongerichte simpele graaf $G$ met $n$ toppen die geen deelgraaf $K_r$ omvat, heeft hoogstens $\frac{(r-2)n^2}{2r-2}$ bogen . ### 4.8 Koppelingen (Matchings) **Definitie 37.** Een **koppeling** (matching) in een ongerichte (multi)graaf $G$ is een verzameling bogen waarin geen twee bogen een top gemeenschappelijk hebben . **Definitie 38.** Een koppeling is **maximaal** indien ze niet kan uitgebreid worden tot een koppeling met meer bogen. Een **maximumkoppeling** is een koppeling van maximale grootte. Een top is **K-verzadigd** indien hij deel uitmaakt van een boog in $K$; anders **K-onverzadigd**. Een **volledige koppeling** verzadigt alle toppen . **Definitie 39.** Een **K-wisselpad** is een pad waarvan de opeenvolgende bogen afwisselend wel en niet tot $K$ behoren. Een **vergrotend K-wisselpad** is een K-wisselpad waarvan de eerste en laatste top K-onverzadigd zijn . **Stelling 48 (Petersen, 1891).** Een koppeling $K$ in een ongerichte graaf $G$ is een maximumkoppeling als en slechts als er in $G$ geen vergrotend $K$-wisselpad bestaat . ### 4.9 Toewijzingen en het lessenroosterprobleem **Definitie 40.** Een **complete bipartiete graaf** $K_{m,n}$ is een bipartiete graaf $G=(V_1 \cup V_2, E)$ waarbij elke top in $V_1$ adjacent is met elke top in $V_2$, met $|V_1|=m$ en $|V_2|=n$ . * De ster $S_n$ is eigenlijk $K_{1,n}$ . **Definitie 41.** Een **toewijzing** (assignment) van $W \subseteq V_1$ in $V_2$ is een koppeling $K$ tussen toppen van $W$ en $V_2$ die alle toppen van $W$ verzadigt . * Een **maximale toewijzing** (respectievelijk volledige toewijzing) is een toewijzing waarbij de bijbehorende koppeling maximaal (respectievelijk volledig) is . **Stelling 49 (P. Hall, 1935).** Een bipartiete ongerichte graaf $G=(V_1 \cup V_2, E)$ heeft een toewijzing van $V_1$ in $V_2$ als en slechts als voor elke deelverzameling $W \subseteq V_1$ geldt dat $|H(W)| \ge |W|$, waarbij $H(W)$ de verzameling van buren van toppen in $W$ is . **Hongaarse methode:** Een algoritme voor het vinden van een maximumtoewijzing door iteratief te zoeken naar vergrotende K-wisselpaden . **Stelling 50 (König).** Voor een bipartiete ongerichte graaf $G=(V_1 \cup V_2, E)$ is de grootte van een maximumkoppeling $|V_1|$ als $t \le 0$, en $|V_1| - t$ als $t > 0$, waarbij $t:= \max_{W \subseteq V_1} (|W| - |H(W)|)$ . **Definitie 42.** Een **(toppen)overdekking** (vertex cover) van een ongerichte graaf $G$ is een deelverzameling $U \subseteq V(G)$ waarbij elke boog van $G$ minstens één top in $U$ bevat . * Een **minimale overdekking** kan niet verder verkleind worden. * Een **minimumoverdekking** is een overdekking met het kleinste aantal toppen. **Stelling 51 (König–Egerváry, 1931).** Voor een bipartiete ongerichte graaf $G=(V_1 \cup V_2, E)$ geldt $\max |K| = \min |U|$, waarbij $K$ de verzameling van alle koppelingen van $G$ doorloopt en $U$ de verzameling van alle overdekkingen van $G$ . ### 4.10 Planaire grafen **Definitie 43.** Een multigraaf is **planair** indien hij in een vlak getekend kan worden zonder dat twee bogen elkaar snijden . * De complete bipartiete graaf $K_{3,3}$ is niet planair . * De complete graaf $K_5$ is niet planair . **Stelling 52 (Euler).** Voor een samenhangende planaire ongerichte multigraaf $G$ geldt altijd $v - e + f = 2$, waarbij $v$ het aantal toppen, $e$ het aantal bogen en $f$ het aantal gebieden is . **Stelling 53.** Een samenhangende planaire ongerichte simpele graaf $G$ met minstens twee bogen voldoet aan $3f \le 2e$ en $e \le 3v - 6$ . **Gevolg 13.** Elke samenhangende planaire ongerichte simpele graaf $G$ heeft een top van graad $\le 5$ . **Definitie 44.** Een graaf $H$ is **boogequivalent** met $G$ indien $H$ ontstaat uit $G$ door het herhaaldelijk toepassen van: 1. Verwijderen van een boog die deel uitmaakt van een cyclus, waarbij de overige bogen blijven. 2. Verbinden van de twee eindpunten van een boog met een nieuwe boog (als de oorspronkelijke boog verwijderd wordt). 3. Verdelen van een boog $\{x, y\}$ in twee bogen $\{x, t\}$ en $\{t, y\}$ met een nieuwe top $t$ . **Stelling 54 (Kuratowski, 1930).** Een multigraaf is planair als en slechts als hij geen deelgraaf bevat die boogequivalent is met $K_{3,3}$ of met $K_5$ . #### 4.10.1 Platonische lichamen De vijf Platonische lichamen (tetraëder, kubus, octaëder, dodecaëder, icosaëder) corresponderen met planaire grafen waarbij elke boog deel is van twee gebieden, elke top graad $n$ heeft, en alle gebieden $m$ bogen hebben. Dit leidt tot de ongelijkheid $(n-2)(m-2) < 4$ . #### 4.10.2 Het kleuren van planaire grafen **Definitie 45.** De **duale graaf** $G^*$ van een planaire ongerichte multigraaf $G$ heeft als toppen de gebieden van $G$. Twee toppen zijn adjacent in $G^*$ als de overeenkomstige gebieden in $G$ een boog delen . **Stelling 55.** Elke samenhangende planaire ongerichte simpele graaf kan met 6 kleuren gekleurd worden . **Stelling 56.** Elke samenhangende planaire ongerichte simpele graaf kan met 5 kleuren gekleurd worden . * De **vierkleurenstelling** (bewezen met computerhulp door Appel en Haken) stelt dat elke samenhangende planaire ongerichte simpele graaf met 4 kleuren gekleurd kan worden . --- # Genererende functies en recurrentievergelijkingen Dit hoofdstuk introduceert genererende functies als een krachtig hulpmiddel voor het oplossen van telproblemen en behandelt lineaire recurrentievergelijkingen met behulp van karakteristieke vergelijkingen en genererende functies. ## 5.1 Voorbeelden en definitie Genererende functies maken het mogelijk om telproblemen te vertalen naar het manipuleren van veeltermen of machtreeksen. De coëfficiënt van een bepaalde term $x^k$ in het product van veeltermen correspondeert met het aantal manieren om een probleem met een som van $k$ te oplossen . ### 5.1.1 Voorbeeld 1: Snoepjesverdeling Een moeder verdeelt 12 snoepjes onder drie kinderen: Piet, Andres en Jan. Piet krijgt minstens 4, Andres en Jan minstens 2, en Jan hoogstens 5. Dit kan worden gemodelleerd door de som $c_P + c_A + c_J = 12$ met de voorwaarden $c_P \ge 4$, $c_A \ge 2$, en $2 \le c_J \le 5$. Het aantal oplossingen is gelijk aan de coëfficiënt van $x^{12}$ in het product van veeltermen: $(x^4 + x^5 + x^6 + x^7 + x^8)(x^2 + x^3 + x^4 + x^5 + x^6)(x^2 + x^3 + x^4 + x^5)$ . ### 5.1.2 Voorbeeld 2: Knikkerkeuze We kiezen 24 knikkers uit vier kleuren (rood, groen, wit, zwart) met de voorwaarden dat er een even aantal witte knikkers is en minstens 6 zwarte. De genererende functie hiervoor is: $(1 + x + x^2 + \dots + x^{18})^2 (1 + x^2 + x^4 + \dots + x^{18}) (x^6 + x^7 + \dots + x^{24})$. Het antwoord is de coëfficiënt van $x^{24}$ in dit product . ### 5.1.3 Definitie van genererende functie Zij $a_0, a_1, a_2, \dots$ een rij van reële getallen. De genererende functie voor deze rij is: $$f(x) = a_0 + a_1x + a_2x^2 + \dots = \sum_{i=0}^{\infty} a_ix^i$$ . #### Voorbeelden van genererende functies * De rij $\binom{n}{0}, \binom{n}{1}, \binom{n}{2}, \dots, \binom{n}{n}, 0, 0, \dots$ heeft de genererende functie $\sum_{i=0}^{n} \binom{n}{i} x^i = (1+x)^n$ . * De rij $1, 1, 1, \dots$ heeft de genererende functie $\frac{1}{1-x} = 1 + x + x^2 + \dots$, voor $|x| < 1$ . * De rij $1, 2, 3, \dots$ heeft de genererende functie $\frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + \dots$ . * De rij $0, 1, 2, 3, \dots$ heeft de genererende functie $\frac{x}{(1-x)^2} = x + 2x^2 + 3x^3 + \dots$ . * De rij $1^2, 2^2, 3^2, \dots$ heeft de genererende functie $\frac{1+x}{(1-x)^3}$ . * De rij $0^2, 1^2, 2^2, \dots$ heeft de genererende functie $\frac{x(1+x)}{(1-x)^3}$ . * De rij $1, 1, 0, 1, 1, 1, \dots$ kan worden gegenereerd door $\frac{1}{1-x} - x^2$ . > **Tip:** Het slim combineren en manipuleren van bekende genererende functies kan leiden tot genererende functies voor nieuwe rijen. ## 5.2 Veralgemeende binomiaalcoëfficiënten Het concept van de binomiaalcoëfficiënt $\binom{n}{r}$ wordt uitgebreid naar niet-gehele waarden van $n$ . ### 5.2.1 Definitie van veralgemeende binomiaalcoëfficiënt Voor $n \in \mathbb{Z}$ en $r \in \mathbb{N}_0$ definiëren we: $$\binom{n}{r}:= \frac{n(n-1)(n-2)\dots(n-r+1)}{r!}$$ . Er geldt ook: $$\binom{-n}{r} = (-1)^r \binom{n+r-1}{r}$$ . En $\binom{n}{0}:= 1$ voor alle $n \in \mathbb{Z}$ . De McLaurinreeks voor $(1+x)^{-n}$ is: $$(1+x)^{-n} = \sum_{r=0}^{\infty} \binom{-n}{r} x^r$$ . Dit is een veralgemening van de binomium van Newton. ### 5.2.2 Voorbeelden met veralgemeende binomiaalcoëfficiënten * **Coëfficiënt van $x^5$ in $(1-2x)^{-7}$:** We passen het veralgemeend binomium toe: $$(1 + (-2x))^{-7} = \sum_{r=0}^{\infty} \binom{-7}{r} (-2x)^r$$ De gezochte coëfficiënt is: $$\binom{-7}{5} (-2)^5 = \binom{11}{5} (-32) (-1)^5 = 462 \cdot (-32) \cdot (-1) = 14784$$ . * **Verdeling van snoepjes met restricties:** 24 snoepjes verdelen onder 4 kinderen, waarbij elk minstens 3 en hoogstens 8 krijgt. De genererende functie is $f(x) = (x^3 + x^4 + \dots + x^8)^4$. We zoeken de coëfficiënt van $x^{24}$. $$f(x) = x^{12} \left(\frac{1-x^6}{1-x}\right)^4 = x^{12} (1-x^6)^4 (1-x)^{-4}$$ We zoeken de coëfficiënt van $x^{12}$ in $(1-x^6)^4 (1-x)^{-4}$. $$(1-x^6)^4 = \binom{4}{0} - \binom{4}{1}x^6 + \binom{4}{2}x^{12} - \dots$$ $$(1-x)^{-4} = \sum_{k=0}^{\infty} \binom{-4}{k} (-x)^k = \sum_{k=0}^{\infty} \binom{k+4-1}{k} x^k = \sum_{k=0}^{\infty} \binom{k+3}{3} x^k$$ De coëfficiënt van $x^{12}$ in het product is: $$1 \cdot \binom{12+3}{3} - \binom{4}{1} \cdot \binom{6+3}{3} + \binom{4}{2} \cdot \binom{0+3}{3}$$ $$= \binom{15}{3} - 4 \binom{9}{3} + 6 \binom{3}{3} = 455 - 4 + 6 = 455 - 336 + 6 = 125$$ [1](#page=1) [84](#page=84). * **Deelverzameling zonder opeenvolgende getallen:** Kies een deelverzameling van met 4 elementen zonder opeenvolgende getallen. Dit is equivalent aan het vinden van $c_1, c_2, c_3, c_4, c_5 \in \mathbb{N}$ met $c_1 + c_2 + c_3 + c_4 + c_5 = 14$, $0 \le c_1, c_5$ en $2 \le c_2, c_3, c_4$. De genererende functie is $(1+x+x^2+\dots)^2 (x^2+x^3+\dots)^3 = (1-x)^{-2} (x^2(1-x)^{-1})^3 = x^6 (1-x)^{-5}$. We zoeken de coëfficiënt van $x^{14}$ in dit product, wat overeenkomt met de coëfficiënt van $x^8$ in $(1-x)^{-5}$ [15](#page=15). $$\binom{-5}{8} (-1)^8 = \binom{8+5-1}{8} = \binom{12}{8} = \binom{12}{4} = \frac{12 \cdot 11 \cdot 10 \cdot 9}{4 \cdot 3 \cdot 2 \cdot 1} = 495$$ . ## 5.3 Partities van natuurlijke getallen Een partitie van een natuurlijk getal $n$ is een schrijf van $n$ als som van niet-nul natuurlijke getallen . ### 5.3.1 Voorbeeld: Zendtijd Het aantal manieren om $n$ minuten reclame te maken met spots van 15, 30 en 60 seconden. In eenheden van 15 seconden is dit $a + 2b + 4c = 4n$. De genererende functie is: $$f(x) = (1+x+x^2+\dots)(1+x^2+x^4+\dots)(1+x^4+x^8+\dots) = \frac{1}{1-x} \frac{1}{1-x^2} \frac{1}{1-x^4}$$ . Het antwoord is de coëfficiënt van $x^{4n}$. ### 5.3.2 Definitie van partitie Een partitie van een niet-nul natuurlijk getal $n$ is een schrijf van $n$ als som van niet-nulle natuurlijke getallen . Notatie: $p(n)$ is het aantal partities van $n$. $p =1, p =2, p =3, p =5, p =7$ [1](#page=1) [2](#page=2) [3](#page=3) [4](#page=4) [5](#page=5). De genererende functie voor $p(n)$ is: $$P(x) = \prod_{i=1}^{\infty} \frac{1}{1-x^i} = \frac{1}{1-x} \frac{1}{1-x^2} \frac{1}{1-x^3} \dots$$ . ### 5.3.3 Partities met verschillende termen $p^{\neq}(n)$ is het aantal partities van $n$ waarbij alle termen verschillend zijn. De genererende functie is: $$P^{\neq}(x) = \prod_{i=1}^{\infty} (1+x^i) = (1+x)(1+x^2)(1+x^3)\dots$$ . ### 5.3.4 Partities met oneven termen $p^{odd}(n)$ is het aantal partities van $n$ waarbij alle termen oneven zijn. De genererende functie is: $$P^{odd}(x) = \prod_{i=1}^{\infty} \frac{1}{1-x^{2i-1}} = \frac{1}{1-x} \frac{1}{1-x^3} \frac{1}{1-x^5} \dots$$ . ### 5.3.5 Stelling: Gelijke aantallen partities Voor elk niet-nul natuurlijk getal $n$ geldt $p^{\neq}(n) = p^{odd}(n)$ . **Bewijs:** Dit volgt uit het feit dat hun genererende functies gelijk zijn: $$P^{\neq}(x) = \prod_{i=1}^{\infty} (1+x^i) = \prod_{i=1}^{\infty} \frac{1-x^{2i}}{1-x^i} = \frac{\prod_{i=1}^{\infty} (1-x^{2i})}{\prod_{i=1}^{\infty} (1-x^i)} = \frac{\prod_{j=1}^{\infty} (1-x^{2j})}{\prod_{j=1}^{\infty} (1-x^{2j}) \prod_{j=1}^{\infty} (1-x^{2j-1})} = \prod_{j=1}^{\infty} \frac{1}{1-x^{2j-1}} = P^{odd}(x)$$ . ### 5.3.6 Young tableau Een Young tableau is een grafische voorstelling van een partitie. Transponeren van een Young tableau toont aan dat het aantal partities van $n$ met $m$ termen gelijk is aan het aantal partities van $n$ waarbij de grootste term $m$ is . ## 5.4 Beroemde genererende functies Een samenvatting van veelgebruikte genererende functies : * $(1+x)^n = \sum_{i=0}^n \binom{n}{i} x^i$ . * $\frac{1-x^{n+1}}{1-x} = \sum_{i=0}^n x^i$ . * $\frac{1}{1-x} = \sum_{i=0}^{\infty} x^i$ . * $\frac{1}{(1+x)^n} = \sum_{i=0}^{\infty} \binom{-n}{i} x^i = \sum_{i=0}^{\infty} (-1)^i \binom{n+i-1}{i} x^i$ . * $\frac{1}{(1-x)^n} = \sum_{i=0}^{\infty} \binom{n+i-1}{i} x^i$ . ## 6. Recurrentievergelijkingen Recurrentievergelijkingen definiëren een rij waarbij de $n$-de term wordt uitgedrukt als een functie van voorgaande termen . De algemene vorm is $a_n = f(a_{n-1}, a_{n-2}, \dots, a_{n-k})$ voor $n \ge k$ . ### 6.1 Homogene eerste orde lineaire recurrentievergelijkingen Deze vergelijkingen hebben de vorm $a_n = r a_{n-1}$ . * **Kenmerken:** * Eerste orde: $a_n$ hangt enkel af van $a_{n-1}$ . * Lineair: enkel eerste machten van $a_{n-1}$ komen voor . * Homogeen: geen termen onafhankelijk van $a_{n-1}$ . * Constante coëfficiënten: $r$ hangt niet af van $n$ . Deze vergelijkingen beschrijven meetkundige rijen. **Stelling 58:** Zij $r \in \mathbb{C}$ en $a_0 \in \mathbb{C}$. De oplossing van $a_{n+1} = r a_n$ is $a_n = r^n a_0$ . #### Voorbeelden * Los $a_{n+1} = 3a_n$ op met $a_0 = 5$. Oplossing: $a_n = 3^n \cdot 5$ . * Los $a_n = 7a_{n-1}$ op met $a_2 = 98$. Oplossing: $a_n = 7^n \cdot 2$ . * Het patroon $0, 2, 6, 12, 20, 30, 42, \dots$ volgt $a_n = n^2 + n$. Dit kan worden afgeleid door de verschillen te bekijken: $a_n - a_{n-1} = 2n$ . ### 6.2 Homogene tweede orde lineaire recurrentievergelijkingen De algemene vorm is $c_0 a_n + c_1 a_{n-1} + c_2 a_{n-2} = 0$, met $c_0, c_2 \neq 0$ . De methode is gebaseerd op het vinden van een *karakteristieke vergelijking*: $$c_0 r^2 + c_1 r + c_2 = 0$$ . De oplossingen van deze kwadratische vergelijking bepalen de vorm van de algemene oplossing. #### 6.2.1 Twee reële wortels Als de karakteristieke vergelijking twee verschillende reële wortels $r_1$ en $r_2$ heeft, is de algemene oplossing: $$a_n = c_1 r_1^n + c_2 r_2^n$$ . De constanten $c_1$ en $c_2$ worden bepaald door beginvoorwaarden. * **Voorbeeld:** $a_n + a_{n-1} - 6a_{n-2} = 0$ met $a_0 = 1, a_1 = 2$. Karakteristieke vergelijking: $r^2 + r - 6 = 0 \implies (r-2)(r+3) = 0$. Wortels zijn $r_1 = 2, r_2 = -3$. Algemene oplossing: $a_n = c_1 2^n + c_2 (-3)^n$. Beginvoorwaarden geven het stelsel: $\begin{cases} 1 = c_1 + c_2 \\ 2 = 2c_1 - 3c_2 \end{cases}$ Oplossing: $c_1 = 1, c_2 = 0$. Dus $a_n = 2^n$ . * **Fibonacci-rij:** $F_{n+2} = F_{n+1} + F_n$ met $F_0 = 0, F_1 = 1$. Karakteristieke vergelijking: $r^2 - r - 1 = 0$. Wortels zijn $r^{\pm} = \frac{1 \pm \sqrt{5}}{2}$ (gulden snede $\phi$ en $1-\phi$). Algemene oplossing: $F_n = c_1 \left(\frac{1+\sqrt{5}}{2}\right)^n + c_2 \left(\frac{1-\sqrt{5}}{2}\right)^n$. Beginvoorwaarden geven $c_1 = \frac{1}{\sqrt{5}}, c_2 = -\frac{1}{\sqrt{5}}$. **Formule van Binet:** $F_n = \frac{1}{\sqrt{5}} \left( \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right)$ . * **Deelverzamelingen zonder opeenvolgende getallen:** $a_n = a_{n-1} + a_{n-2}$ met $a_0 = 1, a_1 = 2$. Dit leidt tot $a_n = F_{n+2}$ . #### Hogere orde lineaire homogene recurrentievergelijkingen Voor hogere orde vergelijkingen, zoals $c_0a_n + c_1a_{n-1} + \dots + c_ka_{n-k} = 0$, wordt de karakteristieke vergelijking $c_0r^k + c_1r^{k-1} + \dots + c_k = 0$ . * **Voorbeeld:** $2a_{n+3} = a_{n+2} + 2a_{n+1} - a_n$ met $a_0=0, a_1=1, a_2=2$. Karakteristieke vergelijking: $2r^3 - r^2 - 2r + 1 = 0 \implies (2r-1)(r-1)(r+1) = 0$. Wortels zijn $r_1 = 1/2, r_2 = 1, r_3 = -1$. Algemene oplossing: $a_n = c_1 ^n + c_2(-1)^n + c_3(1/2)^n$ [1](#page=1). Met beginvoorwaarden wordt dit $a_n = \frac{5}{2} + \frac{1}{6}(-1)^n - \frac{8}{3} \left(\frac{1}{2}\right)^n$ . #### 6.2.2 Twee complex toegevoegde wortels Als de karakteristieke vergelijking complexe wortels $z = \rho(\cos\theta + i\sin\theta)$ en $\bar{z} = \rho(\cos\theta - i\sin\theta)$ heeft, kan de oplossing worden uitgedrukt met behulp van goniometrische functies: $$a_n = \rho^n (k_1 \cos(n\theta) + k_2 \sin(n\theta))$$ . * **Voorbeeld:** $a_n = 2(a_{n-1} - a_{n-2})$ met $a_0=1, a_1=2$. Karakteristieke vergelijking: $r^2 - 2r + 2 = 0$. Wortels zijn $r = 1 \pm i$. In goniometrische vorm: $1+i = \sqrt{2}(\cos(\pi/4) + i\sin(\pi/4))$, $1-i = \sqrt{2}(\cos(\pi/4) - i\sin(\pi/4))$. Algemene oplossing: $a_n = (\sqrt{2})^n (k_1 \cos(n\pi/4) + k_2 \sin(n\pi/4))$. Beginvoorwaarden geven $k_1=1, k_2=1$. Oplossing: $a_n = (\sqrt{2})^n (\cos(n\pi/4) + \sin(n\pi/4))$ . #### 6.2.3 Eén reële wortel met multipliciteit twee Als de karakteristieke vergelijking een dubbele wortel $r$ heeft, is de algemene oplossing: $$a_n = c_1 r^n + n c_2 r^n$$ . Als er een wortel $r$ is met multipliciteit $m$, dan bevat het corresponderende deel van de algemene oplossing termen van de vorm $n^j r^n$ voor $j=0, 1, \dots, m-1$ . * **Voorbeeld:** $a_{n+2} = 4a_{n+1} - 4a_n$ met $a_0=1, a_1=3$. Karakteristieke vergelijking: $r^2 - 4r + 4 = 0 \implies (r-2)^2 = 0$. Enige wortel is $r=2$ met multipliciteit 2. Algemene oplossing: $a_n = c_1 2^n + n c_2 2^n$. Beginvoorwaarden geven $c_1=1, c_2=1/2$. Oplossing: $a_n = 2^n + \frac{1}{2} n 2^n = 2^{n-1}(2+n)$ . ### 6.3 Niet-homogene recurrentievergelijkingen Voor een vergelijking van de vorm $c_0 a_n + c_1 a_{n-1} + \dots + c_k a_{n-k} = f(n)$, waarbij $f(n) \neq 0$, bestaat de algemene oplossing uit de som van de algemene oplossing van de gehomogeniseerde vergelijking ($a_n^{(h)}$) en een particuliere oplossing ($a_n^{(p)}$) van de oorspronkelijke vergelijking: $a_n = a_n^{(h)} + a_n^{(p)}$ . De vorm van $a_n^{(p)}$ wordt geraden op basis van de vorm van $f(n)$ . #### Voorbeelden * **Voorbeeld:** $a_n - 3a_{n-1} = 5 \cdot 7^n$ met $a_0 = 2$. Homogene vergelijking: $a_n^{(h)} = c \cdot 3^n$. Particuliere oplossing: probeer $a_n^{(p)} = A \cdot 7^n$. Substitutie geeft $A \cdot 7^n - 3A \cdot 7^{n-1} = 5 \cdot 7^n \implies 7A - 3A = 35 \implies 4A = 35 \implies A = 35/4$. Algemene oplossing: $a_n = c \cdot 3^n + \frac{35}{4} \cdot 7^n$. Beginvoorwaarde $a_0=2$: $2 = c + 35/4 \implies c = 2 - 35/4 = -27/4$. Oplossing: $a_n = -\frac{27}{4} \cdot 3^n + \frac{35}{4} \cdot 7^n$ . * **Torens van Hanoï:** $a_{n+1} = 2a_n + 1$ met $a_0 = 0$. Homogene vergelijking: $a_n^{(h)} = c \cdot 2^n$. Particuliere oplossing: probeer $a_n^{(p)} = A$. Substitutie geeft $A = 2A + 1 \implies A = -1$. Algemene oplossing: $a_n = c \cdot 2^n - 1$. Beginvoorwaarde $a_0=0$: $0 = c - 1 \implies c = 1$. Oplossing: $a_n = 2^n - 1$ . ### 6.4 Beroemde particuliere oplossingen Tabel met vormen van $f(n)$ en bijbehorende $a_n^{(p)}$ : | $f(n)$ | $a_n^{(p)}$ | | :---------------------------------------------- | :------------------------------------------------ | | $c$ | $A$ | | $n^t, t \in \mathbb{N}_0$ | $A_t n^t + A_{t-1} n^{t-1} + \dots + A_1 n + A_0$ | | $r^n, r \in \mathbb{R}$ | $A r^n$ | | $n^t r^n, t \in \mathbb{N}_0, r \in \mathbb{R}$ | $r^n (A_t n^t + A_{t-1} n^{t-1} + \dots + A_1 n + A_0)$ | **Opmerking:** Als $f(n)$ een vorm heeft die al een oplossing is van de homogene vergelijking, dan moet men voor $a_n^{(p)}$ vermenigvuldigen met een geschikte macht van $n$ . ### 6.5 Een methode met genererende functies Genererende functies kunnen ook worden gebruikt om recurrentievergelijkingen op te lossen . * **Voorbeeld:** $a_n - 3a_{n-1} = n$, voor $n \ge 1$, met $a_0 = 1$. Vermenigvuldig de $n$-de vergelijking met $x^n$ en sommeer over $n \ge 1$: $$\sum_{n=1}^{\infty} a_n x^n - 3 \sum_{n=1}^{\infty} a_{n-1} x^n = \sum_{n=1}^{\infty} n x^n$$ Laat $f(x) = \sum_{n=0}^{\infty} a_n x^n$. Dan: $$(f(x) - a_0) - 3x f(x) = \frac{x}{(1-x)^2}$$ $$(f(x) - 1) - 3x f(x) = \frac{x}{(1-x)^2}$$ $$f(x)(1-3x) = 1 + \frac{x}{(1-x)^2} = \frac{(1-x)^2 + x}{(1-x)^2} = \frac{1 - 2x + x^2 + x}{(1-x)^2} = \frac{1-x+x^2}{(1-x)^2}$$ $$f(x) = \frac{1-x+x^2}{(1-x)^2(1-3x)}$$ We ontbinden in partieelbreuken: $$f(x) = \frac{A}{1-x} + \frac{B}{(1-x)^2} + \frac{C}{1-3x}$$ Na berekening vinden we $A = -1/4, B = -1/2, C = 7/4$. $$f(x) = -\frac{1}{4}\frac{1}{1-x} - \frac{1}{2}\frac{1}{(1-x)^2} + \frac{7}{4}\frac{1}{1-3x}$$ De coëfficiënt van $x^n$ is: $$a_n = -\frac{1}{4} - \frac{1}{2}(n+1) + \frac{7}{4}(3^n) = \frac{7}{4} 3^n - \frac{1}{2}n - \frac{3}{4}$$ [1](#page=1). --- ## Veelgemaakte fouten om te vermijden - Bestudeer alle onderwerpen grondig voor examens - Let op formules en belangrijke definities - Oefen met de voorbeelden in elke sectie - Memoriseer niet zonder de onderliggende concepten te begrijpen

| Term | Definition | |------|------------| | Adjacency Matrix (Adjacentiematrix) | Een vierkante matrix die een graaf representeert, waarbij de elementen aangeven of twee toppen verbonden zijn door een boog. | | Adjacentie (Adjacentie) | De relatie tussen twee toppen die door een boog verbonden zijn in een graaf. | | Algemene oplossing (General Solution) | De volledige verzameling van alle mogelijke oplossingen voor een vergelijking of differentiaalvergelijking, inclusief de willekeurige constanten. | | Asymptoot (Asymptote) | Een lijn die een curve nadert, maar deze nooit snijdt, naarmate een variabele naar oneindig gaat. | | Basis van de inductie (Base Case of Induction) | Het eerste deel van een bewijs per inductie, waarbij de propositie wordt bewezen voor de kleinste waarde van de variabele (meestal 0 of 1). | | Bipartiet (Bipartite) | Een graaf waarvan de toppen kunnen worden verdeeld in twee disjuncte verzamelingen, zodanig dat elke boog twee toppen verbindt die tot verschillende verzamelingen behoren. | | Boog (Edge) | Een lijn die twee toppen van een graaf verbindt. | | Boom (Tree) | Een samenhangende, ongerichte graaf zonder cycli. | | Cartesisch product (Cartesian Product) | Het product van twee of meer verzamelingen, waarbij elk element een geordend paar (of tuple) is van elementen uit de verzamelingen. | | Complexe getallen (Complex Numbers) | Getallen van de vorm a + bi, waarbij a en b reële getallen zijn en i de imaginaire eenheid is ($i^2 = -1$). | | Congruentie (Congruence) | Een relatie tussen twee gehele getallen, zodanig dat hun verschil deelbaar is door een gegeven geheel getal (de modulus). | | Cyclus (Cycle) | Een pad in een graaf dat begint en eindigt bij dezelfde top, en waarbij geen andere toppen of bogen worden herhaald (een gesloten pad). | | Deelgraf (Subgraph) | Een graaf waarvan de toppen en bogen deelverzamelingen zijn van de toppen en bogen van een grotere graaf. | | Deelverzameling (Subset) | Een verzameling waarvan alle elementen ook elementen zijn van een andere, grotere verzameling. | | Determinant (Determinant) | Een scalair getal dat aan een vierkante matrix is geassocieerd en belangrijke eigenschappen van de matrix beschrijft, zoals of de matrix inverteerbaar is. | | Discriminant (Discriminant) | Het deel van de kwadratische formule dat onder het wortelteken staat, dat de aard van de wortels bepaalt (reëel, complex, dubbel). | | Domein (Domain) | De verzameling van alle invoerwaarden waarvoor een functie gedefinieerd is. | | Duiventilprincipe (Pigeonhole Principle) | Als meer items dan containers worden geplaatst, moet ten minste één container meer dan één item bevatten. | | Element (Element) | Een individueel object dat behoort tot een verzameling. | | Equivalentie (Equivalence) | Een relatie die reflexief, symmetrisch en transitief is. | | Equivalentierelatie (Equivalence Relation) | Een relatie op een verzameling die reflexief, symmetrisch en transitief is, die de verzameling partitioneert in disjuncte equivalentieklassen. | | Eulerpad (Eulerian Path) | Een pad in een graaf dat elke boog precies één keer doorkruist. | | Euclidisch algoritme (Euclidean Algorithm) | Een algoritme om de grootste gemene deler van twee gehele getallen te vinden door herhaaldelijk de deling met rest toe te passen. | | Eulerfunctie (Euler's Totient Function) | De functie $\phi(n)$ die telt hoeveel positieve gehele getallen kleiner dan of gelijk aan $n$ relatief priem zijn met $n$. | | Factoring (Ontbinden in factoren) | Het proces van het opsplitsen van een getal of een veelterm in zijn componenten die vermenigvuldigd kunnen worden om het originele object te verkrijgen. | | Fibonacci getallen (Fibonacci Numbers) | Een rij getallen waarbij elke term de som is van de twee voorgaande, beginnend met 0 en 1 (0, 1, 1, 2, 3, 5, ...). | | Functie (Function) | Een relatie tussen twee verzamelingen waarbij elk element van de eerste verzameling precies één element van de tweede verzameling toestaat. | | Genererende functie (Generating Function) | Een formele machtreeks die wordt gebruikt om een rij van getallen te representeren, waarbij de coëfficiënten van de reeks de termen van de rij zijn. | | Getaltheorie (Number Theory) | Het wiskundige studiegebied dat zich bezighoudt met de eigenschappen van gehele getallen, zoals deelbaarheid, priemgetallen en congruenties. | | Gehele getallen (Integers) | De verzameling van positieve en negatieve hele getallen, inclusief nul (... -2, -1, 0, 1, 2 ...). | | Graf (Graph) | Een wiskundig object bestaande uit een verzameling toppen en een verzameling bogen die paren van toppen verbinden. | | Graaf met lussen (Graph with Loops) | Een graaf die bogen toestaat die een top met zichzelf verbinden. | | Grote gemene deler (Greatest Common Divisor - GCD) | Het grootste positieve gehele getal dat twee of meer gehele getallen deelt zonder rest. | | Grootste gemene deler (ggd) | De grootste positieve integer die beide getallen deelt. | | Gulden snede (Golden Ratio) | Een irrationeel getal, ongeveer gelijk aan 1.618, dat vaak voorkomt in de natuur en kunst, en wordt aangeduid met de Griekse letter phi ($\phi$). | | Hamiltoncyclus (Hamiltonian Cycle) | Een cyclus in een graaf die elke top precies één keer bezoekt. | | Hamiltongraaf (Hamiltonian Graph) | Een graaf die een Hamiltoncyclus bevat. | | Hamiltonpad (Hamiltonian Path) | Een pad in een graaf dat elke top precies één keer bezoekt. | | Homogene vergelijking (Homogeneous Equation) | Een vergelijking waarbij alle termen een variabele bevatten, of een vergelijking waarbij alle termen nul zijn aan de rechterzijde. | | Idem (Idem) | "Hetzelfde", wordt gebruikt om te verwijzen naar een voorgaande uitspraak of voorwaarde. | | Impliciete vorm (Implicit Form) | Een vergelijking of relatie die niet expliciet een variabele uitdrukt in termen van andere variabelen. | | Inclusie-Exclusie Principe (Inclusion-Exclusion Principle) | Een telmethode die wordt gebruikt om de grootte van de unie van verzamelingen te berekenen, rekening houdend met overlappingen. | | Inductie (Induction) | Een bewijsmethode die wordt gebruikt om te bewijzen dat een stelling waar is voor alle natuurlijke getallen. | | Infimum (Infimum) | De grootste ondergrens van een verzameling. | | Injectie (Injective Function) | Een functie waarbij elk element in het codomein maximaal één keer wordt afgebeeld; dus, als $f(a) = f(b)$, dan moet $a = b$. | | Invers (Inverse) | Een bewerking die de oorspronkelijke bewerking ongedaan maakt (bijvoorbeeld, het additieve invers is $a + (-a) = 0$; het multiplicatieve invers is $a \times a^{-1} = 1$). | | Invers beeld (Inverse Image) | Het beeld van een verzameling onder de inverse van een functie. | | Inverse functie (Inverse Function) | Een functie die de werking van een oorspronkelijke functie ongedaan maakt. | | Karakteristieke vergelijking (Characteristic Equation) | Een veeltermvergelijking die wordt geassocieerd met een lineaire recurrentievergelijking of differentiaalvergelijking, waarvan de wortels de basis vormen voor de oplossingen. | | Knopen (Nodes) | Synoniem voor toppen in een graaf. | | Komen voor (Occur) | Beschrijft de aanwezigheid of het voorkomen van een element of eigenschap. | | Kortste pad (Shortest Path) | Een pad tussen twee toppen in een graaf met het minimale totale gewicht van de bogen. | | Kwantor (Quantifier) | Een logisch symbool dat aangeeft hoeveel elementen in een verzameling voldoen aan een bepaalde eigenschap (bv. $\forall$ voor 'voor alle', $\exists$ voor 'er bestaat'). | | Kwadratische vergelijking (Quadratic Equation) | Een vergelijking van de vorm $ax^2 + bx + c = 0$. | | Lichaam (Field) | Een commutatieve ring waarin elk niet-nul element een multiplicatief invers heeft. | | Lineaire recurrentie (Linear Recurrence) | Een relatie waarbij de volgende term in een rij wordt berekend als een lineaire combinatie van voorgaande termen. | | Logica (Logic) | Het formele bestuderen van redeneringen en bewijzen, vaak met behulp van symbolische taal. | | Modulair rekenen (Modular Arithmetic) | Een rekenkunde die zich bezighoudt met de resten van delingen, waarbij getallen 'congruent' worden genoemd als ze dezelfde rest hebben bij deling door een modulus. | | Modulus (Modulus) | Het getal waardoor wordt gedeeld in de rekenkunde van congruenties. | | Maximumkoppeling (Maximum Matching) | Een koppeling in een graaf met het grootste mogelijke aantal bogen. | | Multigraf (Multigraph) | Een graaf die meerdere bogen tussen hetzelfde paar toppen en lussen toestaat. | | Natuurlijke getallen (Natural Numbers) | De positieve gehele getallen $\{1, 2, 3, ...\}$ of soms inclusief nul $\{0, 1, 2, 3, ...\}$. | | Negatie (Negation) | De logische operatie die een ware bewering onwaar maakt en een onware bewering waar. | | Niet-homogeen (Non-homogeneous) | Een vergelijking die niet voldoet aan de voorwaarden van homogeniteit, vaak doordat er een constante term of een functie van de variabelen aan één zijde staat. | | Notatie (Notation) | Een systeem van symbolen dat wordt gebruikt om wiskundige concepten en bewerkingen weer te geven. | | Oefening (Exercise) | Een taak of probleem dat wordt gegeven om de begrip en toepassing van de stof te testen. | | Oneindige verzameling (Infinite Set) | Een verzameling die niet eindig is; het heeft een oneindig aantal elementen. | | Ongerichte graaf (Undirected Graph) | Een graaf waarbij de bogen geen richting hebben. | | Ontbinding in priemfactoren (Prime Factorization) | Het proces van het opsplitsen van een samengesteld getal in een product van priemgetallen. | | Opspannende boom (Spanning Tree) | Een deelgraaf van een graaf die alle toppen bevat en een boom is. | | Oplossing (Solution) | Een set waarden voor de variabelen die een vergelijking of stelsel van vergelijkingen waar maken. | | Optelling (Addition) | Een van de vier basisrekenkundige bewerkingen, waarbij getallen worden samengevoegd. | | Orde (Order) | Het hoogste aantal voorgaande termen waar een term van afhangt in een recurrentievergelijking. | | Pad (Path) | Een reeks opeenvolgende bogen en toppen in een graaf die begint en eindigt bij verschillende toppen. | | Partitie (Partition) | 1. Een verdeling van een verzameling in disjuncte deelverzamelingen. 2. Een manier om een geheel getal te schrijven als een som van positieve gehele getallen. | | Permutatie (Permutation) | Een rangschikking van een set elementen in een specifieke volgorde. | | Planaire graaf (Planar Graph) | Een graaf die kan worden getekend in het vlak zonder dat bogen elkaar kruisen. | | Polynoom (Polynomial) | Een veelterm, een uitdrukking bestaande uit variabelen en coëfficiënten, die alleen de bewerkingen van optelling, aftrekking, vermenigvuldiging en niet-negatieve gehele exponenten van variabelen gebruikt. | | Priemgetal (Prime Number) | Een natuurlijk getal groter dan 1 dat geen positieve delers heeft anders dan 1 en zichzelf. | | Principe van de welgeordendheid (Well-Ordering Principle) | Elk niet-leeg deelverzameling van de natuurlijke getallen heeft een kleinste element. | | Propositie (Proposition) | Een bewering die waar of onwaar is. | | Public Key Cryptography (Publieke Sleutel Cryptografie) | Een cryptografisch systeem dat twee sleutels gebruikt: een publieke sleutel voor encryptie en een private sleutel voor decryptie. | | Puzzel (Puzzle) | Een probleem dat wordt gepresenteerd ter vermaak of om een bepaald concept te illustreren. | | Kwantor (Quantifier) | Een logisch symbool dat aangeeft hoeveel elementen in een verzameling voldoen aan een bepaalde eigenschap (bv. $\forall$ voor 'voor alle', $\exists$ voor 'er bestaat'). | | Kwadratische vergelijking (Quadratic Equation) | Een vergelijking van de vorm $ax^2 + bx + c = 0$. | | Lichaam (Field) | Een commutatieve ring waarin elk niet-nul element een multiplicatief invers heeft. | | Lineaire recurrentie (Linear Recurrence) | Een relatie waarbij de volgende term in een rij wordt berekend als een lineaire combinatie van voorgaande termen. | | Logica (Logic) | Het formele bestuderen van redeneringen en bewijzen, vaak met behulp van symbolische taal. | | Modulair rekenen (Modular Arithmetic) | Een rekenkunde die zich bezighoudt met de resten van delingen, waarbij getallen 'congruent' worden genoemd als ze dezelfde rest hebben bij deling door een modulus. | | Modulus (Modulus) | Het getal waardoor wordt gedeeld in de rekenkunde van congruenties. | | Maximumkoppeling (Maximum Matching) | Een koppeling in een graaf met het grootste mogelijke aantal bogen. | | Multigraf (Multigraph) | Een graaf die meerdere bogen tussen hetzelfde paar toppen en lussen toestaat. | | Natuurlijke getallen (Natural Numbers) | De positieve gehele getallen $\{1, 2, 3, ...\}$ of soms inclusief nul $\{0, 1, 2, 3, ...\}$. | | Negatie (Negation) | De logische operatie die een ware bewering onwaar maakt en een onware bewering waar. | | Niet-homogeen (Non-homogeneous) | Een vergelijking die niet voldoet aan de voorwaarden van homogeniteit, vaak doordat er een constante term of een functie van de variabelen aan één zijde staat. | | Notatie (Notation) | Een systeem van symbolen dat wordt gebruikt om wiskundige concepten en bewerkingen weer te geven. | | Oefening (Exercise) | Een taak of probleem dat wordt gegeven om de begrip en toepassing van de stof te testen. | | Oneindige verzameling (Infinite Set) | Een verzameling die niet eindig is; het heeft een oneindig aantal elementen. | | Ongerichte graaf (Undirected Graph) | Een graaf waarbij de bogen geen richting hebben. | | Ontbinding in priemfactoren (Prime Factorization) | Het proces van het opsplitsen van een samengesteld getal in een product van priemgetallen. | | Opspannende boom (Spanning Tree) | Een deelgraaf van een graaf die alle toppen bevat en een boom is. | | Oplossing (Solution) | Een set waarden voor de variabelen die een vergelijking of stelsel van vergelijkingen waar maken. | | Optelling (Addition) | Een van de vier basisrekenkundige bewerkingen, waarbij getallen worden samengevoegd. | | Orde (Order) | Het hoogste aantal voorgaande termen waar een term van afhangt in een recurrentievergelijking. | | Pad (Path) | Een reeks opeenvolgende bogen en toppen in een graaf die begint en eindigt bij verschillende toppen. | | Partitie (Partition) | 1. Een verdeling van een verzameling in disjuncte deelverzamelingen. 2. Een manier om een geheel getal te schrijven als een som van positieve gehele getallen. | | Permutatie (Permutation) | Een rangschikking van een set elementen in een specifieke volgorde. | | Planaire graaf (Planar Graph) | Een graaf die kan worden getekend in het vlak zonder dat bogen elkaar kruisen. | | Polynoom (Polynomial) | Een veelterm, een uitdrukking bestaande uit variabelen en coëfficiënten, die alleen de bewerkingen van optelling, aftrekking, vermenigvuldiging en niet-negatieve gehele exponenten van variabelen gebruikt. | | Priemgetal (Prime Number) | Een natuurlijk getal groter dan 1 dat geen positieve delers heeft anders dan 1 en zichzelf. | | Principe van de welgeordendheid (Well-Ordering Principle) | Elk niet-leeg deelverzameling van de natuurlijke getallen heeft een kleinste element. | | Propositie (Proposition) | Een bewering die waar of onwaar is. | | Public Key Cryptography (Publieke Sleutel Cryptografie) | Een cryptografisch systeem dat twee sleutels gebruikt: een publieke sleutel voor encryptie en een private sleutel voor decryptie. | | Puzzel (Puzzle) | Een probleem dat wordt gepresenteerd ter vermaak of om een bepaald concept te illustreren. | | Recurrente betrekking (Recurrence Relation) | Een vergelijking die een rij definieert door een relatie tussen opeenvolgende termen. | | Recurrentievergelijking (Recurrence Relation) | Een vergelijking die een relatie tussen opeenvolgende termen van een rij definieert. | | Relatie (Relation) | Een verzameling van geordende paren die een verbinding of associatie tussen elementen aangeeft. | | Residue class (Restklasse) | Een verzameling van gehele getallen die congruent zijn modulo een gegeven getal. | | Restklasse (Residue Class) | De verzameling van alle gehele getallen die dezelfde rest hebben bij deling door een gegeven modulus. | | Ring (Ring) | Een algebraïsche structuur met twee bewerkingen (optelling en vermenigvuldiging) die bepaalde axioma's vervullen, zoals associativiteit en distributiviteit. | | Ring met eenheid (Ring with Unity) | Een ring die een multiplicatief identiteitselement (eenheid) heeft. | | Samenhangend (Connected) | Een graaf waarin er voor elk paar toppen een pad bestaat dat hen verbindt. | | Semigroep (Semigroup) | Een verzameling met een associatieve binaire bewerking. | | Simpel (Simple) | Een graaf die geen lussen en geen meerdere bogen tussen hetzelfde paar toppen heeft. | | Singleton (Singleton) | Een verzameling die slechts één element bevat. | | Somprincipe (Sum Rule) | Als er $k$ disjuncte verzamelingen zijn, is de grootte van hun unie gelijk aan de som van hun groottes. | | Stelling (Theorem) | Een wiskundige bewering die is bewezen. | | Stelling van B´ezout (B´ezout's Identity) | Voor twee gehele getallen $a$ en $b$, bestaan er gehele getallen $x$ en $y$ zodanig dat $ax + by = \text{ggd}(a, b)$. | | Stelling van Cayley (Cayley's Formula) | Het aantal genummerde bomen met $n$ toppen is $n^{n-2}$. | | Stelling van De Moivre (De Moivre's Theorem) | Een formule voor het verheffen van een complex getal in goniometrische vorm tot een macht: $(r(\cos \theta + i \sin \theta))^n = r^n(\cos(n\theta) + i \sin(n\theta))$. | | Stelling van Euler (Euler's Theorem) | Als $a$ en $n$ relatief priem zijn, dan $a^{\phi(n)} \equiv 1 \pmod{n}$. | | Stelling van Hall (Hall's Marriage Theorem) | In een bipartiete graaf $G = (V_1 \cup V_2, E)$, bestaat er een koppeling die alle toppen van $V_1$ dekt als en slechts als voor elke deelverzameling $W \subseteq V_1$, $|N(W)| \ge |W|$. | | Stelling van Kirchoff (Kirchoff's Theorem) | Het aantal opspannende bomen in een graaf is gelijk aan elke cofactor van zijn Laplaciaanse matrix. | | Stelling van Kuratowski (Kuratowski's Theorem) | Een graaf is planair als en slechts als hij geen deelgraaf heeft die isomorf is met $K_5$ of $K_{3,3}$. | | Stelling van Tur´an (Tur´an's Theorem) | Geeft een bovengrens voor het aantal bogen in een graaf die een bepaalde complete deelgraaf $K_r$ niet bevat. | | Stelling van Vander-monde (Vander-monde's Identity) | $\sum_{k=0}^r \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$. | | Substitutie (Substitution) | Het vervangen van een variabele of uitdrukking door een andere. | | Surjectie (Surjective Function) | Een functie waarbij elk element in het codomein minstens één keer wordt afgebeeld; dus, voor elke $b$ in het codomein, bestaat er een $a$ in het domein zodanig dat $f(a) = b$. | | Synthese (Synthesis) | Het combineren van verschillende delen om een geheel te vormen. | | Systeem (System) | Een verzameling onderling gerelateerde elementen die samenwerken om een doel te bereiken. | | Tautologie (Tautology) | Een logische uitspraak die altijd waar is, ongeacht de waarheidswaarden van zijn componenten. | | Teltechnieken (Counting Techniques) | Methoden om het aantal manieren te berekenen waarop gebeurtenissen kunnen plaatsvinden. | | Toewijzing (Assignment) | Een koppeling tussen elementen van twee verzamelingen, vaak gebruikt in de context van het koppelen van taken aan personen of middelen. | | Top (Vertex/Node) | Een knooppunt in een graaf. | | Transductie (Transduction) | Het proces van het omzetten van een vorm van energie of informatie in een andere. | | Transitiviteit (Transitivity) | Een eigenschap van een relatie waarbij, als $a$ gerelateerd is aan $b$ en $b$ aan $c$, dan is $a$ ook gerelateerd aan $c$. | | Twee-kleurenstelling (Two-Color Theorem) | Een graaf is tweekleurig (bipartiet) als en slechts als hij geen cycli van oneven lengte bevat. | | Uitgraad (Out-degree) | Het aantal bogen die uit een top vertrekken in een gerichte graaf. | | Unie van verzamelingen (Union of Sets) | De verzameling die alle elementen bevat die in ten minste één van de gegeven verzamelingen voorkomen. | | Universum (Universe) | De verzameling van alle mogelijke elementen die in een bepaald domein van discussie worden beschouwd. | | Variabele (Variable) | Een symbool dat een waarde vertegenwoordigt die kan veranderen of niet is gespecificeerd. | | Verzameling (Set) | Een collectie van distincte objecten. | | Verzamelingentheorie (Set Theory) | Het wiskundige studiegebied dat zich bezighoudt met verzamelingen. | | Vierkantswortel (Square Root) | Een getal dat, wanneer het met zichzelf wordt vermenigvuldigd, een gegeven getal oplevert. | | Volledige koppeling (Perfect Matching) | Een koppeling in een graaf waarbij elke top van de graaf deel uitmaakt van precies één boog in de koppeling. | | Welorde (Well-Ordering) | Een eigenschap van een verzameling waarbij elke niet-lege deelverzameling een kleinste element heeft. | | Welgeordendheid (Well-Ordering) | Een eigenschap van een verzameling waarbij elke niet-lege deelverzameling een kleinste element heeft. | | Woord (Word) | Een geordende reeks van symbolen uit een bepaald alfabet. | | Wortel (Root) | Een waarde van de variabele die een vergelijking waar maakt; in het bijzonder voor veeltermen, een waarde $z_0$ zodanig dat $P(z_0) = 0$. |

# Introduzione alle sommatorie e proprietà Questo argomento introduce il concetto di sommatoria, la sua notazione e le proprietà fondamentali, inclusi esempi di applicazione [1](#page=1). ### 1.1 Definizione di sommatoria La sommatoria è una notazione compatta utilizzata per esprimere la somma di una sequenza di termini [1](#page=1). #### 1.1.1 Notazione standard Dati $X_1, X_2, \dots, X_n$, la sommatoria è scritta come: $$ \sum_{i=1}^{n} X_i $$ Questa notazione si legge come "sommatoria di $X_i$ per $i$ che va da 1 a $n$" . Essa rappresenta la somma [1](#page=1): $$ X_1 + X_2 + \dots + X_n $$ #### 1.1.2 Notazione generale Più in generale, dati $n_0$ e $n_1$ tali che $n_0 \le n_1$ e $X_i \in \mathbb{R}$ per ogni $i$, la sommatoria è espressa come: $$ \sum_{i=n_0}^{n_1} X_i $$ Questa notazione indica la somma: $$ X_{n_0} + X_{n_0+1} + \dots + X_{n_1} $$ #### 1.1.3 Esempi di sommatoria * Calcolo di $\sum_{i=1}^{4} i$: $$ \sum_{i=1}^{4} i = 1 + 2 + 3 + 4 = 10 $$ * Calcolo di $\sum_{i=0}^{2} x_i$: $$ \sum_{i=0}^{2} x_i = x_0 + x_1 + x_2 $$ * Calcolo di $\sum_{i=2}^{4} i$: $$ \sum_{i=2}^{4} i = 2 + 3 + 4 = 9 $$ * Calcolo di $\sum_{i=-1}^{1} (i-3)$: $$ \sum_{i=-1}^{1} (i-3) = (-1-3) + (0-3) + (1-3) = -4 + (-3) + (-2) = -9 $$ * Esempio con $n_0=1, n_1=2$ e $x_i = i$: $\sum_{i=1}^{2} i = 1 + 2 = 3$ [1](#page=1). * Esempio con $n_0=1, n_1=4$ e $x_i = i$: $\sum_{i=1}^{4} i = 1 + 2 + 3 + 4 = 10$ [1](#page=1). * Esempio con $n_0=0, n_1=2$ e $x_i = i$: $\sum_{i=0}^{2} i = 0 + 1 + 2 = 3$ [1](#page=1). * Esempio con $n_0=0, n_1=2$ e $x_i = \frac{i}{2}$: $\sum_{i=0}^{2} \frac{i}{2} = \frac{0}{2} + \frac{1}{2} + \frac{2}{2} = 0 + \frac{1}{2} + 1 = \frac{3}{2}$ [1](#page=1). ### 1.2 Proprietà delle sommatorie Le sommatorie possiedono diverse proprietà fondamentali che semplificano i calcoli [2](#page=2). #### 1.2.1 Proprietà di linearità 1. **Moltiplicazione per uno scalare:** Se $c$ è una costante reale, allora: $$ \sum_{i=n_0}^{n_1} c x_i = c \sum_{i=n_0}^{n_1} x_i $$ 2. **Somma di termini:** La sommatoria di una somma è la somma delle sommatorie: $$ \sum_{i=n_0}^{n_1} (x_i + y_i) = \sum_{i=n_0}^{n_1} x_i + \sum_{i=n_0}^{n_1} y_i $$ #### 1.2.2 Proprietà di additività degli intervalli Dati $n_0 \le m \le n_1$: $$ \sum_{i=n_0}^{n_1} x_i = \sum_{i=n_0}^{m} x_i + \sum_{i=m+1}^{n_1} x_i $$ > **Tip:** Questa proprietà è utile per suddividere una sommatoria in intervalli più piccoli o per combinare sommatorie. * **Caso particolare (proprietà 3-bis):** Per $m = n_1-1$: $$ \sum_{i=n_0}^{n_1} x_i = \sum_{i=n_0}^{n_1-1} x_i + x_{n_1} $$ #### 1.2.3 Proprietà di traslazione dell'indice Se $m$ è un intero, si può traslare l'indice della sommatoria: $$ \sum_{i=n_0}^{n_1} x_i = \sum_{j=n_0+m}^{n_1+m} x_{j-m} $$ > **Osservazione:** La proprietà 4 può essere ottenuta con un cambio di indice. Ponendo $j = i+m$, si ha $i = j-m$. > Se $i=n_0$, allora $j=n_0+m$. > Se $i=n_1$, allora $j=n_1+m$. > Quindi: > $$ \sum_{i=n_0}^{n_1} x_i = \sum_{j=n_0+m}^{n_1+m} x_{j-m} $$ > [2](#page=2). ### 1.3 Principio di induzione Il principio di induzione matematica è uno strumento fondamentale per dimostrare che una proprietà $P(n)$ è vera per tutti gli interi $n$ a partire da un certo valore iniziale $n_0$ [2](#page=2). **Teoria:** Sia $n_0 \in \mathbb{N}$. Sia $P(n)$ una proprietà ben definita per ogni $n \ge n_0$. Se si verificano le seguenti condizioni: 1. **Passo base:** $P(n_0)$ è vera. 2. **Passo induttivo:** Per ogni $k \ge n_0$, se $P(k)$ è vera (ipotesi induttiva), allora $P(k+1)$ è vera. Allora, $P(n)$ è vera per ogni intero $n \ge n_0$ [2](#page=2). --- # Principio di induzione matematica Il principio di induzione matematica è un potente strumento di dimostrazione utilizzato per provare la validità di affermazioni relative a tutti i numeri naturali a partire da un certo valore iniziale [3](#page=3). ### 2.1 Formulazione del principio Il principio di induzione matematica può essere enunciato come segue [3](#page=3): **Teorema:** Sia $n_0 \in \mathbb{N}$ e sia $P(n)$ una proprietà ben definita per ogni $n \ge n_0$. Supponiamo che valgano le seguenti due condizioni: 1. $P(n_0)$ è vera (base dell'induzione). 2. Per ogni $n \ge n_0$, se $P(n)$ è vera, allora $P(n+1)$ è vera (passo induttivo). Allora, la proprietà $P(n)$ è vera per ogni $n \in \mathbb{N}$ con $n \ge n_0$. #### 2.1.1 Dimostrazione del principio La dimostrazione del principio di induzione matematica si basa sulla proprietà ben fondata dell'insieme dei numeri naturali, ovvero che ogni sottoinsieme non vuoto di $\mathbb{N}$ ammette un elemento minimo [3](#page=3). Si procede per assurdo: assumiamo che la tesi sia falsa. Ciò significa che esiste almeno un numero naturale $s$, tale che $s \ge n_0$ e $P(s)$ è falsa. Consideriamo l'insieme $S = \{n \in \mathbb{N} \mid n \ge n_0 \text{ e } P(n) \text{ è falsa}\}$. Per l'assunzione fatta, $S$ è un sottoinsieme non vuoto di $\mathbb{N}$ [3](#page=3). Poiché $\mathbb{N}$ è ben ordinato, anche $S$ ammette un elemento minimo, che chiamiamo $\hat{n}$ [3](#page=3). * Se $\hat{n} = n_0$, allora $P(n_0)$ sarebbe falsa, il che contraddice la prima ipotesi del principio di induzione ($P(n_0)$ è vera) [3](#page=3). * Se $\hat{n} > n_0$, allora $P(\hat{n})$ è falsa per definizione di $\hat{n}$. Poiché $\hat{n} > n_0$, allora anche $\hat{n}-1 \ge n_0$. Se $P(\hat{n}-1)$ fosse vera, allora per la seconda ipotesi del principio di induzione (il passo induttivo), $P(\hat{n}-1+1) = P(\hat{n})$ dovrebbe essere vera. Ma questo contraddice il fatto che $P(\hat{n})$ è falsa. Pertanto, $P(\hat{n}-1)$ deve essere falsa. Questo implica che $\hat{n}-1$ appartiene all'insieme $S$. Tuttavia, $\hat{n}-1 < \hat{n}$, il che contraddice il fatto che $\hat{n}$ è l'elemento minimo di $S$ [3](#page=3). Entrambi i casi portano a una contraddizione, quindi l'assunzione iniziale (che la tesi sia falsa) deve essere errata. Pertanto, $P(n)$ è vera per ogni $n \in \mathbb{N}$ con $n \ge n_0$ [3](#page=3). #### 2.1.2 Ipotesti induttiva L'affermazione "$P(n)$ è vera" nella seconda condizione del principio di induzione (per ogni $n \ge n_0$, se $P(n)$ è vera, allora $P(n+1)$ è vera) è chiamata **ipotesi induttiva**. Essa costituisce il presupposto su cui si basa la dimostrazione della validità dell'affermazione per il caso successivo [4](#page=4). ### 2.2 Esempi di applicazione #### 2.2.1 Esempio 1: Somma dei primi n numeri naturali Dimostrare per induzione che la somma dei primi $n$ numeri naturali è data da: $$ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} $$ per ogni $n \ge 1$ [3](#page=3). **Svolgimento:** Definiamo la proprietà $P(n)$ come: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$. Il valore iniziale è $n_0 = 1$. 1. **Base dell'induzione ($P $):** [1](#page=1). Dobbiamo verificare se $P $ è vera [1](#page=1): $$ \sum_{i=1}^{1} i = 1 $$ E il lato destro della formula per $n=1$ è: $$ \frac{1(1+1)}{2} = \frac{1 \cdot 2}{2} = 1 $$ Quindi, $P $ è vera [1](#page=1) [4](#page=4). 2. **Passo induttivo:** Supponiamo che $P(k)$ sia vera per un generico $k \ge 1$ (ipotesi induttiva). Cioè, assumiamo che: $$ \sum_{i=1}^{k} i = \frac{k(k+1)}{2} $$ Dobbiamo dimostrare che $P(k+1)$ è vera, cioè che: $$ \sum_{i=1}^{k+1} i = \frac{(k+1)((k+1)+1)}{2} = \frac{(k+1)(k+2)}{2} $$ Partiamo dal lato sinistro di $P(k+1)$: $$ \sum_{i=1}^{k+1} i = \left(\sum_{i=1}^{k} i\right) + (k+1) $$ Applicando l'ipotesi induttiva $\left(\sum_{i=1}^{k} i = \frac{k(k+1)}{2}\right)$: $$ = \frac{k(k+1)}{2} + (k+1) $$ Mettiamo in evidenza $(k+1)$: $$ = (k+1) \left(\frac{k}{2} + 1\right) $$ $$ = (k+1) \left(\frac{k+2}{2}\right) $$ $$ = \frac{(k+1)(k+2)}{2} $$ Questo è esattamente il lato destro di $P(k+1)$. Pertanto, il passo induttivo è verificato [4](#page=4). Poiché entrambe le condizioni sono verificate, per il principio di induzione matematica, la formula $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ è vera per ogni $n \ge 1$ [4](#page=4). #### 2.2.2 Esempio 2: Somma di una progressione geometrica Dimostrare per induzione che vale la seguente formula per la somma di una progressione geometrica con primo termine $a$ e ragione $r \ne 1$: $$ \sum_{i=0}^{n} ar^i = a \frac{1-r^{n+1}}{1-r} $$ per ogni $n \in \mathbb{N}$ ($n \ge 0$), con $a \in \mathbb{R}$, $r \in \mathbb{R}$, $r \ne 1$ [5](#page=5). **Svolgimento:** Per semplicità nell'esempio fornito, consideriamo il caso $a=1$ e $r=2$, ottenendo la formula: $$ \sum_{i=0}^{n} 2^i = \frac{1-2^{n+1}}{1-2} $$ La proprietà $P(n)$ è: $\sum_{i=0}^{n} 2^i = \frac{1-2^{n+1}}{1-2}$. Il valore iniziale è $n_0 = 0$. 1. **Base dell'induzione ($P $):** . Verifichiamo $P $ : $$ \sum_{i=0}^{0} 2^i = 2^0 = 1 $$ Il lato destro della formula per $n=0$ è: $$ \frac{1-2^{0+1}}{1-2} = \frac{1-2^1}{1-2} = \frac{1-2}{-1} = \frac{-1}{-1} = 1 $$ Quindi, $P $ è vera [5](#page=5). 2. **Passo induttivo:** Supponiamo che $P(k)$ sia vera per un generico $k \ge 0$ (ipotesi induttiva). Cioè, assumiamo che: $$ \sum_{i=0}^{k} 2^i = \frac{1-2^{k+1}}{1-2} $$ Dobbiamo dimostrare che $P(k+1)$ è vera, cioè che: $$ \sum_{i=0}^{k+1} 2^i = \frac{1-2^{(k+1)+1}}{1-2} = \frac{1-2^{k+2}}{1-2} $$ Partiamo dal lato sinistro di $P(k+1)$: $$ \sum_{i=0}^{k+1} 2^i = \left(\sum_{i=0}^{k} 2^i\right) + 2^{k+1} $$ Applicando l'ipotesi induttiva $\left(\sum_{i=0}^{k} 2^i = \frac{1-2^{k+1}}{1-2}\right)$: $$ = \frac{1-2^{k+1}}{1-2} + 2^{k+1} $$ Per sommare, troviamo un denominatore comune, che è $1-2$: $$ = \frac{1-2^{k+1}}{1-2} + \frac{2^{k+1}(1-2)}{1-2} $$ $$ = \frac{1-2^{k+1} + 2^{k+1} - 2^{k+1} \cdot 2}{1-2} $$ $$ = \frac{1 - 2^{k+1} + 2^{k+1} - 2^{k+2}}{1-2} $$ $$ = \frac{1 - 2^{k+2}}{1-2} $$ Questo è il lato destro di $P(k+1)$. Pertanto, il passo induttivo è verificato [5](#page=5). Poiché le condizioni 1 e 2 sono soddisfatte, il principio di induzione assicura che la formula vale per ogni $n \ge 0$ [5](#page=5). > **Tip:** Quando si applica il principio di induzione, è fondamentale definire chiaramente la proprietà $P(n)$ e identificare correttamente il valore iniziale $n_0$. > **Tip:** Durante il passo induttivo, ricordarsi di utilizzare esplicitamente l'ipotesi induttiva per semplificare l'espressione. Non si può dimostrare $P(n+1)$ assumendo che sia già vera. --- # Progressioni geometriche e applicazioni finanziarie Questo argomento esplora il concetto di progressione geometrica e illustra la sua applicazione nel calcolo di accumulazioni e ammortamenti di debiti in contesti finanziari [5](#page=5) [6](#page=6) [7](#page=7). ### 3.1 Progressioni geometriche Una progressione geometrica è una successione di numeri in cui ciascun termine, dopo il primo, si ottiene moltiplicando il termine precedente per una costante diversa da zero, detta ragione [5](#page=5). La formula generale per la somma dei primi $n+1$ termini di una progressione geometrica con primo termine $a$ e ragione $r$ è data da: $$ S_{n+1} = \sum_{i=0}^{n} ar^i $$ Se $r \neq 1$, la somma è: $$ S_{n+1} = a \frac{1-r^{n+1}}{1-r} $$ [5](#page=5). #### 3.1.1 Dimostrazione per induzione La validità della formula per la somma di una progressione geometrica può essere dimostrata per induzione [5](#page=5). * **Passo base (n=0):** Verificare che la formula sia vera per $n=0$. $$ \sum_{i=0}^{0} ar^i = ar^0 = a $$ Usando la formula: $$ a \frac{1-r^{0+1}}{1-r} = a \frac{1-r}{1-r} = a $$ L'ipotesi è verificata per $n=0$ [5](#page=5). * **Passo induttivo:** Assumere che la formula sia vera per un generico $n=k$, ovvero $\sum_{i=0}^{k} ar^i = a \frac{1-r^{k+1}}{1-r}$. Dimostrare che è vera anche per $n=k+1$. $$ \sum_{i=0}^{k+1} ar^i = \left(\sum_{i=0}^{k} ar^i\right) + ar^{k+1} $$ Applicando l'ipotesi induttiva: $$ = a \frac{1-r^{k+1}}{1-r} + ar^{k+1} $$ $$ = a \frac{1-r^{k+1} + r^{k+1}(1-r)}{1-r} $$ $$ = a \frac{1-r^{k+1} + r^{k+1} - r^{k+2}}{1-r} $$ $$ = a \frac{1-r^{k+2}}{1-r} $$ La formula è verificata per $n=k+1$ [5](#page=5). #### 3.1.2 Osservazioni sulla progressione geometrica Si osservano alcune proprietà e casi particolari della formula [6](#page=6): * Se $a=1$ e $r=2$, la somma è $\sum_{i=0}^{n} 2^i = \frac{1-2^{n+1}}{1-2} = 2^{n+1}-1$ [6](#page=6). * Per $n=1$, la progressione è $a + ar$. La formula diventa $a \frac{1-r^2}{1-r} = a(1+r)$, che corrisponde a $a+ar$ [6](#page=6). * Per $n=2$, la progressione è $a + ar + ar^2$. La formula diventa $a \frac{1-r^3}{1-r} = a(1+r+r^2)$, che corrisponde a $a+ar+ar^2$. Questo illustra la relazione con i prodotti notevoli, come $(A-B)(A+B) = A^2-B^2$ e $(A-B)(A^2+AB+B^2) = A^3-B^3$ [6](#page=6). ### 3.2 Applicazioni finanziarie Le progressioni geometriche sono fondamentali per modellare operazioni finanziarie come l'accumulazione di capitali (investimenti) e l'ammortamento di debiti [5](#page=5) [6](#page=6) [7](#page=7). #### 3.2.1 Accumulazione di capitali Quando si effettuano investimenti periodici, il capitale accumulato alla fine di un certo periodo può essere calcolato utilizzando la formula della progressione geometrica [6](#page=6). > **Esempio:** Se si investono 50 euro ogni anno a partire dal 1.1.2026 con un rendimento annuo del 3%, si desidera calcolare l'ammontare accumulato al 1.1.2029 [6](#page=6). > > * **1.1.2026:** Capitale investito = 50 euro. > * **1.1.2027:** Capitale = $50 \times (1.03) + 50$. (Il primo investimento è maturato del 3%, il secondo è appena stato versato) [6](#page=6). > * **1.1.2028:** Capitale = $[50 \times (1.03) + 50 \times (1.03) + 50 = 50 \times (1.03)^2 + 50 \times (1.03) + 50$ [6](#page=6). > * **1.1.2029:** Capitale = $50 \times (1.03)^3 + 50 \times (1.03)^2 + 50 \times (1.03) + 50$ [6](#page=6). > > Questo ammontare può essere scritto come una somma di una progressione geometrica: > $$ \sum_{i=0}^{3} 50 \times (1.03)^i $$ > Applicando la formula della progressione geometrica con $a=50$, $r=1.03$ e $n=3$: > $$ 50 \frac{1-(1.03)^{3+1}}{1-1.03} = 50 \frac{1-(1.03)^4}{1-1.03} $$ > Questo calcolo porta all'ammontare totale accumulato [7](#page=7). #### 3.2.2 Ammortamento di debiti Analogamente, il calcolo delle rate fisse per estinguere un debito, comprensivo degli interessi maturati, si basa sul medesimo principio [7](#page=7). > **Esempio:** Se una banca presta 50 euro il 1.1.2026 con un tasso d'interesse annuo del 4% sul debito residuo, si vuole determinare la rata fissa annuale ($x$) necessaria per estinguere il debito al 1.1.2029 [7](#page=7). > > * **1.1.2026:** Debito iniziale = 50 euro. > * **1.1.2027:** Debito residuo = $50 \times (1.04) - x$. (Il debito iniziale aumenta del 4%, viene poi pagata la rata $x$) [7](#page=7). > * **1.1.2028:** Debito residuo = $[50 \times (1.04) - x \times (1.04) - x = 50 \times (1.04)^2 - x(1.04) - x$ [7](#page=7). > * **1.1.2029:** Debito residuo = $[50 \times (1.04)^2 - x(1.04) - x \times (1.04) - x = 50 \times (1.04)^3 - x(1.04)^2 - x(1.04) - x$ [7](#page=7). > > Affinché il debito sia estinto, il debito residuo al 1.1.2029 deve essere zero: > $$ 50 \times (1.04)^3 - x \sum_{i=0}^{2} (1.04)^i = 0 $$ > Utilizzando la formula della progressione geometrica per la somma $\sum_{i=0}^{2} (1.04)^i$ con $a=1$, $r=1.04$ e $n=2$: > $$ \sum_{i=0}^{2} (1.04)^i = 1 \times \frac{1-(1.04)^{2+1}}{1-1.04} = \frac{1-(1.04)^3}{1-1.04} $$ > Imponendo il debito residuo a zero: > $$ 50 \times (1.04)^3 = x \frac{1-(1.04)^3}{1-1.04} $$ > Da questa equazione si può ricavare il valore della rata $x$ [7](#page=7). > **Tip:** È cruciale prestare attenzione alla definizione del periodo di riferimento e alla corretta applicazione della formula della progressione geometrica sia per il montante che per l'ammortamento, tenendo conto del numero di termini ($n+1$) e del fattore di capitalizzazione ($r$) [6](#page=6) [7](#page=7). --- # Fattoriali e coefficienti binomiali Questa sezione introduce le definizioni di fattoriali e coefficienti binomiali, analizzandone le proprietà fondamentali e la formula del binomio di Newton. ### 4.1 Fattoriali #### 4.1.1 Definizione di fattoriale Per ogni numero intero non negativo $n$, il fattoriale, denotato con $n!$, è definito come: * $n! = 1$ se $n=0$ [7](#page=7). * $n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1$ se $n > 0$ [7](#page=7). #### 4.1.2 Proprietà del fattoriale Una proprietà immediata del fattoriale è la seguente relazione ricorsiva: $n! = n \times (n-1)!$ per $n > 0$ [8](#page=8). #### 4.1.3 Esempi di fattoriali * $0! = 1$ [8](#page=8). * $1! = 1$ [8](#page=8). * $2! = 2 \times 1 = 2$ [8](#page=8). * $3! = 3 \times 2 \times 1 = 3 \times 2! = 3 \times 2 = 6$ [8](#page=8). * $4! = 4 \times 3! = 4 \times 6 = 24$ [8](#page=8). * $5! = 5 \times 4! = 5 \times 24 = 120$ [8](#page=8). ### 4.2 Coefficienti binomiali #### 4.2.1 Definizione di coefficiente binomiale Dati due numeri interi $n$ e $k$ tali che $n \ge k \ge 0$, il coefficiente binomiale, letto come "n su k" o "n scegli k", è definito come: $$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$ Questo rappresenta il numero di modi per scegliere $k$ elementi da un insieme di $n$ elementi distinti, senza considerare l'ordine [8](#page=8). #### 4.2.2 Proprietà dei coefficienti binomiali Siano $n, k$ interi con $n \ge k \ge 0$. Valgono le seguenti proprietà: 1. **Valori agli estremi:** $$ \binom{n}{0} = 1 $$ $$ \binom{n}{n} = 1 $$ Queste proprietà derivano direttamente dalla definizione e dal fatto che $0! = 1$ [8](#page=8). 2. **Simmetria:** $$ \binom{n}{k} = \binom{n}{n-k} $$ Questa proprietà è evidente sostituendo $k$ con $n-k$ nel denominatore: $k!(n-k)! = (n-k)!(n-(n-k))! = (n-k)!k!$ [8](#page=8). > **Tip:** La proprietà di simmetria può semplificare i calcoli, poiché $\binom{n}{k}$ è uguale a $\binom{n}{n-k}$. Ad esempio, calcolare $\binom{10}{7}$ è equivalente a calcolare $\binom{10}{3}$, che spesso è più veloce. 3. **Relazione di Pascal:** $$ \binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k} $$ Questa identità è fondamentale e permette di costruire il triangolo di Tartaglia (o Pascal). La sua dimostrazione si basa sull'uso della definizione dei coefficienti binomiali e sulle proprietà dei fattoriali [8](#page=8). > **Tip:** La relazione di Pascal può essere dimostrata per induzione o manipolando algebricamente la definizione. Una dimostrazione combinatoria, pensando a come contare un sottoinsieme di dimensione $k$ da un insieme di $n+1$ elementi, può essere molto intuitiva. 4. **Formula per il calcolo diretto (derivata dalla definizione):** Per $k > 0$, possiamo scrivere: $$ \binom{n}{k} = \frac{n(n-1)(n-2)\dots(n-k+1)}{k!} $$ Questa formula è utile quando $k$ è significativamente più piccolo di $n$, evitando di calcolare fattoriali molto grandi per $n!$ e $(n-k)!$ [8](#page=8). ### 4.3 La formula del binomio di Newton La formula del binomio di Newton fornisce uno sviluppo in serie per la potenza di un binomio $(a+b)^n$. Essa stabilisce che: $$ (a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k $$ dove $n$ è un intero non negativo, e $a, b$ sono numeri reali con $a \ne 0$ e $b \ne 0$ [9](#page=9). Questa formula può essere riscritta come: $$ (a+b)^n = \binom{n}{0} a^n b^0 + \binom{n}{1} a^{n-1} b^1 + \binom{n}{2} a^{n-2} b^2 + \dots + \binom{n}{n-1} a^1 b^{n-1} + \binom{n}{n} a^0 b^n $$ #### 4.3.1 Dimostrazione della formula del binomio di Newton Le dimostrazioni per le proprietà 1, 2 e 5 dei coefficienti binomiali si basano direttamente sulla loro definizione [9](#page=9). La dimostrazione completa della formula del binomio di Newton viene solitamente effettuata per induzione matematica [9](#page=9). > **Tip:** La formula del binomio di Newton è estremamente utile per espandere potenze di espressioni binarie senza dover eseguire moltiplicazioni ripetute. I coefficienti binomiali fungono da coefficienti di ogni termine nell'espansione. #### 4.3.2 Esempio di applicazione della formula del binomio di Newton Consideriamo l'espansione di $(a+b)^3$: Utilizzando la formula con $n=3$: $$ (a+b)^3 = \sum_{k=0}^{3} \binom{3}{k} a^{3-k} b^k $$ Calcoliamo i coefficienti binomiali necessari: * $\binom{3}{0} = 1$ * $\binom{3}{1} = 3$ * $\binom{3}{2} = 3$ * $\binom{3}{3} = 1$ Sostituendo questi valori nell'espansione: $$ (a+b)^3 = \binom{3}{0} a^3 b^0 + \binom{3}{1} a^2 b^1 + \binom{3}{2} a^1 b^2 + \binom{3}{3} a^0 b^3 $$ $$ (a+b)^3 = 1 \cdot a^3 \cdot 1 + 3 \cdot a^2 \cdot b + 3 \cdot a \cdot b^2 + 1 \cdot 1 \cdot b^3 $$ $$ (a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3 $$ --- ## Errori comuni da evitare - Rivedete tutti gli argomenti accuratamente prima degli esami - Prestate attenzione alle formule e definizioni chiave - Praticate con gli esempi forniti in ogni sezione - Non memorizzate senza comprendere i concetti sottostanti

| Termine | Definizione | |------|------------| | Sommatoria | La sommatoria, indicata con il simbolo greco Sigma ($\Sigma$), è una notazione matematica utilizzata per rappresentare la somma di una sequenza di numeri o termini. | | Principio di induzione | Un metodo di dimostrazione matematica utilizzato per provare che una proprietà P(n) è vera per tutti i numeri interi naturali a partire da un certo valore iniziale $n_0$. | | Ipotesi induttiva | Nel principio di induzione, è l'assunzione che la proprietà P(n) sia vera per un generico intero $n \geq n_0$. | | Passo induttivo | Nel principio di induzione, è la dimostrazione che, se P(n) è vera (ipotesi induttiva), allora anche P(n+1) è vera. | | Progressione geometrica | Una successione di numeri in cui ogni termine, dopo il primo, si ottiene moltiplicando il termine precedente per una costante fissa chiamata ragione. | | Ragione (di una progressione geometrica) | La costante fissa per cui si moltiplica ogni termine per ottenere il successivo in una progressione geometrica. | | Capitale | La somma di denaro iniziale investita o presa in prestito. | | Rendita | Un pagamento periodico, spesso utilizzato in contesti finanziari come investimenti o mutui. | | Fattoriale | Per un numero intero non negativo $n$, il fattoriale (indicato con $n!$) è il prodotto di tutti gli interi positivi minori o uguali a $n$. Per definizione, $0! = 1$. | | Coefficiente binomiale | Indicato con $\binom{n}{k}$, rappresenta il numero di modi per scegliere $k$ elementi da un insieme di $n$ elementi senza riguardo all'ordine. Si calcola come $\frac{n!}{k!(n-k)!}$. | | Binomio di Newton | Una formula che esprime la potenza $n$-esima di un binomio $(a+b)$ come somma di termini, ciascuno dei quali è un coefficiente binomiale moltiplicato per potenze di $a$ e $b$. |