Volledige inductie

Volledige inductie kan worden geïllustreerd aan de hand van het domino-effect.

In de wiskunde is volledige inductie een methode om te bewijzen dat een uitspraak geldig is voor alle natuurlijke getallen. Het is de bekendste vorm van wiskundige inductie.

Omdat er oneindig veel natuurlijke getallen zijn, kan een dergelijk bewijs niet voor elk getal afzonderlijk worden geleverd. Volledige inductie houdt in de meest gebruikelijke vorm in dat het bewijs wordt geleverd voor het getal 0 en dat wordt bewezen dat als de uitspraak geldig is voor enig natuurlijk getal, de uitspraak ook geldig is voor de opvolger van dit getal. Zonder dat voor ieder natuurlijk getal de uitspraak afzonderlijk is bewezen, kan men nu concluderen dat ze voor elk natuurlijk getal $n$ geldig is. Uit de geldigheid voor 0 volgt immers de geldigheid voor 1 en uit de geldigheid voor 1 volgt die voor 2, enzovoort. Zo volgt de geldigheid voor ieder getal $n$.

Na bewezen te hebben dat als de uitspraak geldig is voor enig natuurlijk getal, de uitspraak ook geldig is voor de opvolger van dit getal, heeft het bewijs leveren voor het getal 0 een domino-effect: het correspondeert met het omduwen van de eerste domino; het successievelijk omvallen van elke volgende domino correspondeert met het successievelijke bewijs voor elk volgende getal.

Geschiedenis

De methode van de volledige inductie werd, hoewel niet formeel beschreven, in de klassieke oudheid wel al gebruikt. Francesco Maurolico (1494-1575), een wiskundige uit Sicilië, gebruikte in zijn werk de methode van volledige inductie ook. Blaise Pascal wordt gezien als de eerste die de volledige inductie formeel beschreef, maar hij was op de hoogte van het werk van Maurolico. De onderstaande behandeling van de volledige inductie is te danken aan Giuseppe Peano.

Definities

Het principe van volledige inductie is een methode, die in het algemeen wordt gebruikt om te bewijzen dat een uitspraak $E_n$ voor alle natuurlijke getallen $n\ge m$ geldig is. Het bewijs verloopt in twee stappen. De eerste stap, het inductiebegin, is het bewijs dat $E_m$ geldig is. De volgende stap, de inductiestap, is dat uit de veronderstelling dat de uitspraak waar is voor een getal $n\ge m$, de inductieveronderstelling of inductiehypothese, dus dat $E_n$ geldig is, volgt dat de uitspraak ook waar is voor het volgende getal, dus dat $E_{n+1}$ geldig is. Met verwijzing naar het getal $n$ spreekt men ook van volledige inductie naar $n$.

Voor sommige bewijzen wordt het inductiebegin bij het getal 0 gelegd, maar soms ook neemt men het begin bij 1 of bij een groter getal. Dat hangt ervan af voor welke getallen de uitspraak geldig is. Daarom wordt in de definitie het inductiebegin bij een willekeurig getal $m$ gelegd.

Bewijsschema

De definitie laat zich vertalen in de volgende stappen voor het bewijs dat $E_n$ geldig is voor alle natuurlijke getallen $n\ge m$:

Zwakke inductie

1. inductiebegin: bewijs dat $E_m$ geldig is
2. inductieveronderstelling: neem aan dat $E_n$ geldig is voor een getal $n\ge m$
3. inductiestap: bewijs dat uit de inductieveronderstelling volgt dat $E_{n+1}$ geldig is.

Sterke inductie

Soms blijkt het nodig, of handig, als inductieveronderstelling de juistheid van alle uitspraken tot en met de index $n$ te veronderstellen. Dit bewijsschema heet sterke inductie en levert een gelijkwaardige vorm van volledige inductie op.

1. inductiebegin: bewijs dat $E_m$ geldig is
2. inductieveronderstelling: neem aan dat $E_p$ geldig is voor alle $p$ met $m\le p\le n$
3. inductiestap: bewijs dat uit de inductieveronderstelling volgt dat $E_{n+1}$ geldig is.

Beide zijn een vorm van een bewijs met volledige inductie.

Voorbeelden

Voorbeeld 1

De somformule van Gauss voor de getallen 1 tot en met $n$, die geldig is voor alle natuurlijke getallen, is:

$\sum _{k=0}^{n}k=1+2+\dots +n=\frac{1}{2}n(n+1)$

Het bewijs met volledige inductie naar $n$ gaat als volgt.

Inductiebegin

De formule is geldig voor $n=0$, want:

$\sum _{k=0}^{0}k=0=\frac{1}{2}0(0+1)$

Inductieveronderstelling

Veronderstel dat voor een zekere $n$ geldt:

$\sum _{k=0}^{n}k=\frac{1}{2}n(n+1)$

Inductiestap

Voor $n+1$ geldt dan:

$\sum _{k=0}^{n+1}k=\sum _{k=0}^{n}k+(n+1)=\frac{1}{2}n(n+1)+(n+1)=\frac{1}{2}(n+1)(n+2)$,

waarmee, met gebruik van de inductieveronderstelling, de geldigheid voor $n+1$ is aangetoond.

Er is een eenvoudiger bewijs, dat niet van inductie gebruikmaakt.

Voorbeeld 2

Ieder positieve gehele getal $n$, waarbij $n\ge 2$, is door een priemgetal te delen.

Het bewijs gaat met de sterke inductie naar $n$.

Inductiebegin

2 is door een priemgetal te delen, namelijk door 2 zelf.

Inductieveronderstelling

Tot en met $n$ zijn alle getallen door een priemgetal te delen.

Inductiestap

• Voor het geval $n+1$ zelf een priemgetal is, is de inductiestap gedaan.
• Anders zijn er twee getallen $a$ en $b$, zodat $n+1=a\cdot b$. Voor $a$ en $b$ geldt dat $2\le a,b\le n$. De getallen $a$ en $b$ zijn beide volgens de inductieveronderstelling door een priemgetal te delen. Kies een priemgetal $p$ waarvoor geldt dat $a$ door $p$ is te delen. Nu moet $n+1$ ook door $p$ zijn te delen. Daarmee is ook voor dit geval de inductiestap gedaan.

Voorbeeld 3

Een deel van de stelling van Zeckendorf wordt ook bewezen met de tweede vorm van het bewijsschema. Deze stelling zegt dat alle Fibonacci-getallen op een unieke manier de som zijn van een aantal niet opeenvolgende Fibonacci-getallen.

Voorbeeld 4

Om te bewijzen dat de methode van Laplace om een determinant te berekenen dezelfde uitkomst geeft als de methode van Leibniz, wordt de bewijsmethode van volledige inductie gebruikt. Het bewijs gaat met behulp van volledige inductie, omdat de methode van Laplace recursief is en het bewijs deze recursieve stappen ook teruggaat.

Voorbeeld 5

De determinant van Vandermonde $V_n$ van de orde $n$ is als volgt gedefinieerd

$V_n=\left|\begin{array}{cccccc}1& x_1& x_1^2& \dots & x_1^{n-2}& x_1^{n-1}\\ 1& x_2& x_2^2& \dots & x_2^{n-2}& x_2^{n-1}\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 1& x_n& x_n^2& \dots & x_n^{n-2}& x_n^{n-1}\end{array}\right|$

Het aantal variabelen $x_i$ in deze determinant is $n$.

Voor deze determinant geldt:

$V_n=\prod _{1\le i<j\le n}(x_j-x_i)$

Het bewijs hiervan gaat met volledige inductie naar $n$.