3. volledige inductie
Volledige inductie
Een bewijs met volledige inductie heeft de volgende structuur:
- Laat zien dat de bewering waar is voor een zekere $n$.
- Neem aan dat de bewering waar is voor $n$ en laat zien dat de bewering dan ook waar is voor $n+1$.
- Trek de conclusie dat de bewering waar is vanaf zekere $n$.
Het domino-effect
Voor deze methode hoef je de formule maar voor één geval te controleren, namelijk voor n=1. Verder moet je het ‘domino-effect’ aantonen. Dit houdt in dat je van een bewijs van de formule voor een bepaald getal een bewijs kunt maken voor het volgende getal. Het bewijs van de formule voor een bepaald getal kun je je voorstellen als een omgevallen dominosteen. Het domino-effect garandeert dat als de formule voor een bepaald getal 'omgevallen is', de formule ook 'omvalt' voor het volgende getal.
Voorbeeld 1
Te bewijzen: $
1+2+3+...+n=\frac{1}{2}n\left( {n + 1} \right)
$
Stap 1: controleer of de formule klopt voor (bijvoorbeeld $n=1$). Vul in $n=1$:
$
1 = \frac{1}{2} \cdot 1\left( {1 + 1} \right) = 1
$
Klopt.
Stap 2: laat dan zien dat als de formule klopt voor ‘n’ de formule ook klopt voor ‘n+1’. Vul voor $n$ in de formule $n+1$ in:
$
1 + 2 + 3 + .... + n + (n + 1) = \frac{1}{2}\left( {n + 1} \right)\left( {n + 2} \right)
$
Om dit laatste aan te tonen maak je gebruik van de zogenaamde inductieveronderstelling. Dat wil zeggen dat je er van uitgaat dat de formule klopt voor ‘n’. In dit geval kan je ‘links’ het stuk van 1 tot met n vervangen door $
\frac{1}{2}n\left( {n + 1} \right)
$
$
\begin{array}{l}
\underbrace {1 + 2 + 3 + .... + n}_{\frac{1}{2}n(n + 1)} + \left( {n + 1} \right) = \frac{1}{2}\left( {n + 1} \right)\left( {n + 2} \right) \\
\frac{1}{2}n(n + 1) + (n + 1) = \frac{1}{2}\left( {n + 1} \right)\left( {n + 2} \right) \\
\left( {n + 1} \right)\left( {\frac{1}{2}n + 1} \right) = \frac{1}{2}\left( {n + 1} \right)\left( {n + 2} \right) \\
\frac{1}{2}\left( {n + 1} \right)\left( {n + 2} \right) = \frac{1}{2}\left( {n + 1} \right)\left( {n + 2} \right)\\
\end{array}
$
Klopt.
Stap 3: $
1+2+3+...+n=\frac{1}{2}n\left( {n + 1} \right)
$ is waar.
Voorbeeld 2
Te bewijzen: $1^3 + 2^3 + ... + n^3 = \frac{1}{4}n^2 \left( {n + 1} \right)^2$
Stap 1: neem $n=1$
$1^3=1$ en $\frac{1}{4} \cdot 1^2\left( {1+1}\right)^2=1$
Klopt.
Stap 2: neem $n+1$
$1^3+2^3+...+n^3+(n+1)^3$ =
$\frac{1}{4}\left({n+1}\right)^2\left({\left({n+1}\right)+1}\right)^2$
Stap 3: $
1^3 + 2^3 + ... + n^3 = \frac{1}{4}n^2 \left( {n + 1} \right)^2
$ voor $
n \ge 1
$
Voorbeeld 3
Te bewijzen: $
3^{2n + 1} + 2^{n - 1} \,\,{\rm{is}}\,\,{\rm{deelbaar}}\,\,{\rm{door}}\,\,{\rm{7}}
$
Voorbeeld 4
Te bewijzen: $
1^2 + 2^2 + ... + n^2 = \frac{1}{6}\,n\left( {n + 1} \right)\left( {2n + 1} \right)
$
Voorbeeld 5
Te bewijzen: $3n^{2}+3n+6$ is deelbaar door $6$ voor $n \ge 1$