Volledige inductie

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, en dat daarnaast wordt bewezen, dit heet de inductiestap, dat als de uitspraak geldig is voor enig natuurlijk getal, de uitspraak ook geldig is voor de opvolger van dit getal. Zonder dat voor elk natuurlijk getal de uitspraak afzonderlijk is bewezen, kan men nu concluderen dat ze voor elk natuurlijk getal geldig is. Zo is de uitspraak bijvoorbeeld geldig voor het getal 1234567890, want uit de geldigheid voor 0 volgt de geldigheid voor 1 en daaruit weer voor 2, enz. Uiteindelijk volgt in eindig veel stappen ook de geldigheid voor 1234567890.

Men vergelijkt de methode wel 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

Voor het bewijs dat een uitspraak $E_n$ geldig is voor alle natuurlijke getallen $\scriptstyle n \ge m$, is het voldoende te bewijzen dat de uitspraak geldig is voor $n=m$, dus dat $E_m$ geldig is (het inductiebegin), en dat uit de geldigheid voor enig getal $\scriptstyle n \ge m$ (de inductieveronderstelling of -hypothese), de geldigheid volgt van $E_{n+1}$ (de inductiestap). Een dergelijk bewijs heet een bewijs met volledige inductie naar, of specifieker met verwijzing naar het getal $n$ waarmee de uitspraak geïndiceerd is, volledige inductie naar $n$.

Bewijsschema

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.

Soms blijkt het nodig, of handig, als inductieveronderstelling de juistheid van alle uitspraken tot en met de index n te veronderstellen. Het voorbeeld dat alle Fibonacci-getallen de som zijn van een aantal niet opeenvolgende Fibonacci-getallen gaat op deze manier. Het 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.

Beide vormen van bewijs heten in het Nederlands 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+\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

Een deel van de stelling van Zeckendorf wordt bewezen met volledige inductie en wel met de tweede vorm van het bewijsschema.

Voorbeeld 3

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.

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