Som van de eerste n positieve gehele getallen

Bewijs dat $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ voor elke $n \ge 1$.

Basisstap: controleer $n = 1$: Linkerkant: $1$. Rechterkant: $\dfrac{1 \cdot 2}{2} = 1$ = $P(1)$ is waar

Inductiehypothese: neem $P(k)$ aan voor een $k \ge 1$: Stel dat $1 + 2 + \dots + k = \dfrac{k(k+1)}{2}$ = Deze gelijkheid mogen we gebruiken

Inductiestap: tel de volgende term $k+1$ bij beide kanten op: $1 + \dots + k + (k+1) = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{k(k+1) + 2(k+1)}{2}$ = $= \dfrac{(k+1)(k+2)}{2}$

Vergelijk met $P(k+1)$: $P(k+1)$ zegt dat de som gelijk is aan $\dfrac{(k+1)\big((k+1)+1\big)}{2} = \dfrac{(k+1)(k+2)}{2}$ = $P(k+1)$ is waar

Answer: Met volledige inductie geldt $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ voor elke $n \ge 1$. Bijvoorbeeld: $1 + 2 + \dots + 100 = \dfrac{100 \cdot 101}{2} = 5050$.

Som van de eerste n oneven getallen

Bewijs dat $1 + 3 + 5 + \dots + (2n-1) = n^2$ voor elke $n \ge 1$.

Basisstap: controleer $n = 1$: Linkerkant: $1$. Rechterkant: $1^2 = 1$ = $P(1)$ is waar

Inductiehypothese: Stel dat $1 + 3 + \dots + (2k-1) = k^2$ voor een $k \ge 1$ = Deze gelijkheid mogen we gebruiken

Bepaal het volgende oneven getal: Het oneven getal na $2k-1$ is $2(k+1) - 1 = 2k + 1$ = Tel $2k + 1$ op

Inductiestap: $1 + 3 + \dots + (2k-1) + (2k+1) = k^2 + 2k + 1$ = $= (k+1)^2$, dus $P(k+1)$ is waar

Answer: Met volledige inductie is de som van de eerste $n$ oneven getallen gelijk aan $n^2$. Controle: $1 + 3 + 5 + 7 + 9 = 25 = 5^2$.

Som van machten van 2

Bewijs dat $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ voor elke $n \ge 0$.

Basisstap: hier is de eerste waarde $n = 0$: Linkerkant: $2^0 = 1$. Rechterkant: $2^{1} - 1 = 1$ = $P(0)$ is waar

Inductiehypothese: Stel dat $1 + 2 + \dots + 2^k = 2^{k+1} - 1$ voor een $k \ge 0$ = Deze gelijkheid mogen we gebruiken

Inductiestap: tel de volgende term $2^{k+1}$ op: $1 + 2 + \dots + 2^k + 2^{k+1} = 2^{k+1} - 1 + 2^{k+1}$ = $= 2 \cdot 2^{k+1} - 1$

Vereenvoudig en vergelijk met $P(k+1)$: $2 \cdot 2^{k+1} - 1 = 2^{k+2} - 1 = 2^{(k+1)+1} - 1$ = $P(k+1)$ is waar

Answer: Met volledige inductie geldt $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ voor elke $n \ge 0$. Controle voor $n = 6$: $1 + 2 + 4 + 8 + 16 + 32 + 64 = 127 = 2^7 - 1$.

Een bewijs over deelbaarheid

Bewijs dat $n^3 - n$ deelbaar is door $3$ voor elke $n \ge 1$. (In de les Direct bewijs werd dit met ontbinden in factoren getoond; nu gebruiken we inductie.)

Basisstap: controleer $n = 1$: $1^3 - 1 = 0 = 3 \cdot 0$ = $P(1)$ is waar

Inductiehypothese: Stel dat $k^3 - k = 3m$ voor een geheel getal $m$ = $k^3 - k$ is een veelvoud van $3$

Werk de uitdrukking voor $k+1$ uit: $(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1$ = $= (k^3 - k) + 3k^2 + 3k$

Gebruik de inductiehypothese: $(k^3 - k) + 3k^2 + 3k = 3m + 3(k^2 + k)$ = $= 3(m + k^2 + k)$

Concludeer: $m + k^2 + k$ is een geheel getal, dus de uitdrukking is een veelvoud van $3$ = $P(k+1)$ is waar

Answer: Met volledige inductie is $n^3 - n$ deelbaar door $3$ voor elke $n \ge 1$. Controle voor $n = 5$: $125 - 5 = 120 = 3 \cdot 40$.

Een ongelijkheid: 2 tot de macht n is groter dan n

Bewijs dat $2^n > n$ voor elke $n \ge 1$.

Basisstap: controleer $n = 1$: $2^1 = 2$ en $2 > 1$ = $P(1)$ is waar

Inductiehypothese: Stel dat $2^k > k$ voor een $k \ge 1$ = Deze ongelijkheid mogen we gebruiken

Schrijf $2^{k+1}$ met behulp van $2^k$: $2^{k+1} = 2 \cdot 2^k > 2 \cdot k$ = $2^{k+1} > 2k$

Vergelijk $2k$ met $k+1$: $2k = k + k \ge k + 1$, omdat $k \ge 1$ = $2k \ge k + 1$

Koppel de ongelijkheden: $2^{k+1} > 2k \ge k + 1$ = $2^{k+1} > k + 1$, dus $P(k+1)$ is waar

Answer: Met volledige inductie geldt $2^n > n$ voor elke $n \ge 1$. Bijvoorbeeld: $2^{10} = 1024 > 10$.

Mistake: De basisstap overslaan

Why: De inductiestap alleen bewijst niets: die zegt alleen dat ALS een steen valt, de volgende ook valt. Voorbeeld: de onjuiste bewering $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ heeft een inductiestap die werkt, maar voor $n = 1$ is de linkerkant $1$ en de rechterkant $2$.

Correct: Controleer altijd expliciet het eerste geval. Zonder een eerste vallende steen valt er niets.

Mistake: Aannemen wat je wilt bewijzen

Why: Wie "stel dat $P(n)$ waar is voor alle $n$" of "stel dat $P(k+1)$" schrijft, redeneert in een cirkel: de conclusie wordt al aangenomen.

Correct: Neem $P(k)$ aan voor ÉÉN waarde $k$ (de inductiehypothese) en bewijs daarmee $P(k+1)$.

Mistake: Verkeerde algebra in de inductiestap

Why: Een veelgemaakte fout is de verkeerde volgende term optellen, bijvoorbeeld $2k - 1$ in plaats van $2k + 1$ bij de som van oneven getallen, of vergeten de nieuwe term aan één kant op te tellen.

Correct: Schrijf eerst $P(k+1)$ volledig uit (vervang elke $n$ door $k+1$) en werk dan precies naar die uitdrukking toe.

Mistake: Denken dat veel gecontroleerde gevallen een bewijs zijn

Why: De uitdrukking $n^2 + n + 41$ geeft priemgetallen voor $n = 0, 1, \dots, 39$, maar voor $n = 40$ geeft ze $1681 = 41^2$, en dat is geen priemgetal.

Correct: Voorbeelden helpen om een formule te vermoeden. Alleen de basisstap plus de inductiestap bewijzen haar voor elke $n$.

Computerprogramma's controleren

Programmeurs gebruiken inductie om te bewijzen dat een lus na elk aantal rondes het juiste antwoord geeft: klopt het na $k$ rondes, dan klopt het ook na $k+1$ rondes.

Een lus telt $1, 2, 3, \dots$ op bij een lopend totaal. Inductie bewijst dat het totaal na $n$ rondes gelijk is aan $\dfrac{n(n+1)}{2}$.

De Torens van Hanoi

Bij deze puzzel verplaats je een stapel schijven naar een andere pin, steeds één schijf tegelijk, en nooit een grotere schijf op een kleinere. Inductie bewijst dat $n$ schijven $2^n - 1$ zetten nodig hebben.

Om $k+1$ schijven te verplaatsen, zet je de bovenste $k$ schijven opzij, verplaats je de grootste schijf en zet je de $k$ schijven er weer bovenop: $2(2^k - 1) + 1 = 2^{k+1} - 1$ zetten.

Rijstkorrels op het schaakbord

Een oude legende: leg $1$ rijstkorrel op het eerste veld, $2$ op het tweede, $4$ op het derde, en verdubbel steeds. De som van machten van 2 geeft je het totaal.

Op de eerste $3$ velden liggen $1 + 2 + 4 = 7 = 2^3 - 1$ korrels.

Q: Waarom bewijst inductie de uitspraak echt voor ALLE n?

A: De basisstap geeft $P(1)$. De stap met $k = 1$ geeft $P(2)$, met $k = 2$ geeft hij $P(3)$, enzovoort. Elk positief geheel getal wordt na eindig veel stappen bereikt, dus geen enkele $n$ wordt overgeslagen.

Q: Moet de basisstap altijd bij n = 1 liggen?

A: Nee. Begin bij de eerste waarde vanaf waar de uitspraak moet gelden. De som van machten van 2 begint bij $n = 0$. De uitspraak $2^n > n^2$ is onwaar voor $n = 2, 3, 4$ (bijvoorbeeld $2^4 = 16 = 4^2$) en geldt voor elke $n \ge 5$, dus dat bewijs gebruikt de basisstap $n = 5$.

Q: Is volledige inductie hetzelfde als inductief redeneren in de natuurwetenschappen?

A: Nee. Bij inductief redeneren raad je een algemene regel uit voorbeelden, en die kan fout zijn. Volledige inductie is een deductief bewijs: zodra de basisstap en de inductiestap bewezen zijn, staat het resultaat vast.

Q: Wat is sterke inductie?

A: Bij sterke inductie neemt de hypothese aan dat $P(1), P(2), \dots, P(k)$ allemaal waar zijn, niet alleen $P(k)$. Dat is handig als $P(k+1)$ van meerdere eerdere gevallen afhangt, bijvoorbeeld bij bewijzen over ontbinding in priemfactoren.