Volledige inductie

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen
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 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 .

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.

Geschiedenis[bewerken | brontekst bewerken]

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

Definities[bewerken | brontekst bewerken]

Het principe van volledige inductie is een methode om te bewijzen dat een uitspraak geldig is voor alle natuurlijke getallen . Het bewijs verloopt in twee stappen. De eerste stap, het 'inductiebegin', is het bewijs dat geldig is. De volgende stap, de 'inductiestap', is dat uit de veronderstelling dat de uitspraak waar is voor een getal , de inductieveronderstelling of inductiehypothese, dus dat geldig is, volgt dat de uitspraak ook waar is voor het volgende getal, dus dat geldig is. Met verwijzing naar het getal spreekt men ook van volledige inductie naar .

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 gelegd.

Bewijsschema[bewerken | brontekst bewerken]

De definitie laat zich vertalen in de volgende stappen voor het bewijs dat geldig is voor alle natuurlijke getallen :

Zwakke inductie
  1. inductiebegin: bewijs dat geldig is
  2. inductieveronderstelling: neem aan dat geldig is voor een getal
  3. inductiestap: bewijs dat uit de inductieveronderstelling volgt dat geldig is.
Sterke inductie

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

  1. inductiebegin: bewijs dat geldig is
  2. inductieveronderstelling: neem aan dat geldig is voor alle met
  3. inductiestap: bewijs dat uit de inductieveronderstelling volgt dat geldig is.

Beide zijn een vorm van een bewijs met volledige inductie.

Voorbeelden[bewerken | brontekst bewerken]

Voorbeeld 1[bewerken | brontekst bewerken]

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

Het bewijs met volledige inductie naar gaat als volgt.

Inductiebegin

De formule is geldig voor , want:

Inductieveronderstelling

Veronderstel dat voor een zekere geldt:

Inductiestap

Voor geldt dan:

,

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

Er is een eenvoudiger bewijs, zonder gebruikmaking van inductie. Zie daarvoor het artikel Somformule van Gauss.

Voorbeeld 2[bewerken | brontekst bewerken]

Ieder positief geheel getal is door een priemgetal te delen.

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

Inductiebegin
2 is door een priemgetal te delen, namelijk door 2 zelf.
Inductieveronderstelling
Tot en met zijn alle getallen door een priemgetal te delen.
Inductiestap
  • Voor het geval zelf een priemgetal is, is de inductiestap gedaan.
  • Anders zijn er twee getallen en , zodat . Voor en geldt dat . De getallen en zijn beide volgens de inductieveronderstelling door een priemgetal te delen. Kies een priemgetal waarvoor geldt dat door is te delen. Nu moet ook door zijn te delen. Daarmee is ook voor dit geval de inductiestap gedaan.

Voorbeeld 3[bewerken | brontekst 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 | brontekst bewerken]

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

De determinant van Vandermonde van de orde is als volgt gedefinieerd

Het aantal variabelen in deze determinant is .

Voor deze determinant geldt:

Het bewijs hiervan gaat met volledige inductie naar .