Volledige inductie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Een formele beschrijving van wiskundige inductie kan worden geïllustreerd aan de hand van het in de tijd volgordelijke domino-effect.

In de wiskunde is volledige inductie een methode om te bewijzen dat een uitspraak geldig is voor alle natuurlijke getallen. Omdat er oneindig veel natuurlijke getallen zijn, kan een dergelijk bewijs niet voor elk getal afzonderlijk worden geleverd. Volledige inductie houdt in dat het bewijs wordt geleverd voor het getal 0, het inductiebegin of de inductiebasis, en dat daarnaast wordt bewezen dat als de uitspraak geldig is voor enig natuurlijk getal, de uitspraak ook geldig is voor de opvolger van dit getal. Dit heet de inductiestap. Zonder dat voor elk 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, uit die voor 2 die voor 3, enz. Uiteindelijk volgt ook de geldigheid voor n en dit na eindig veel, namelijk n, stappen.

Men vergelijkt de methode soms met het domino-effect. Elke steen die omvalt laat z'n opvolger omvallen. Valt de eerste steen om, dan zullen dus alle stenen omvallen.

Het is niet nodig dat het inductiebegin bij het getal 0 ligt. Soms neemt men het begin bij 1, maar ook kan het begin bij een groter getal liggen, omdat de uitspraak niet geldig is voor kleinere getallen. Daarom wordt in de definitie het inductiebegin bij een willekeurig getal m gelegd.

De onderstaande behandeling van de volledige inductie is te danken aan Giuseppe Peano.

Definitie[bewerken]

Voor het bewijs dat een uitspraak E_n geldig is voor alle natuurlijke getallen \scriptstyle n \ge m, kan eerst bewezen worden dat de uitspraak geldig is voor n=m, dus dat E_m geldig is. Deze eerste stap heet het inductiebegin. De volgende stap is, dat uit de veronderstelling dat de uitspraak waar is voor een getal \scriptstyle n \ge m, dus dat E_n geldig is, de uitspraak ook waar is voor het volgende getal, dus dat E_{n+1} geldig is. De gekozen veronderstelling is de inductieveronderstelling of inductiehypothese, de redenering naar het volgende getal heet de inductiestap. Een dergelijk bewijs heet een bewijs met volledige inductie, of specifieker met verwijzing naar het getal n waarmee de uitspraak geïndexeerd is, volledige inductie naar n.

Bewijsschema[bewerken]

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

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

Versterkte volledige inductie[bewerken]

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_0 geldig is
  2. inductieveronderstelling: neem aan dat E_n geldig is voor alle \scriptstyle m \le n
  3. inductiestap: bewijs dat E_{n+1} geldig is.

Voorbeelden[bewerken]

Voorbeeld 1[bewerken]

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+\cdots+n = \tfrac 12 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 = \tfrac 1 2 0(0+1)
Inductieveronderstelling

Veronderstel dat voor een zekere n geldt:

\sum_{k=0}^n k =\tfrac 12 n(n+1).
Inductiestap

Voor n+1 geldt dan:

\sum_{k=0}^{n+1} k = \sum_{k=0}^n k + (n+1) = \tfrac 12 n(n+1) + (n+1) = \tfrac 12 (n+1)(n+2) ,

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

Er is een eenvoudiger bewijs, zonder gebruikmaking van inductie; zie hier.

Voorbeeld 2[bewerken]

Ieder positief geheel getal n is door een priemgetal te delen.

Het bewijs gaat met volledige inductie naar n volgens de tweede vorm van het bewijsschema.

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\leq a,b\leq 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[bewerken]

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[bewerken]

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

V_n = \begin{vmatrix}
  1 & x_1 & x_1^2 & \cdots & x_1^{n-2} & x_1^{n-1} \\
  1 & x_2 & x_2^2 & \cdots & x_2^{n-2} & x_2^{n-1} \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
  1 & x_n & x_n^2 & \cdots & x_n^{n-2} & x_n^{n-1}
\end{vmatrix}

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.


Bronnen, noten en/of referenties
  • "The theory of the foundations of mathematics - 1870 to 1940" - M. Scheffer
  • "De taal van de wiskunde - een verkenning van wiskundig taalgebruik en logische redeneerpatronen" - R.P. Nederpelt, Uitgeverij Versluys, ISBN 90-249-1696-8