title: Volledige inductie
text: 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 .
  
  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  voor alle natuurlijke getallen  geldig is. 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 
  De definitie laat zich vertalen in de volgende stappen voor het bewijs dat  geldig is voor alle natuurlijke getallen :
   Zwakke inductie
   inductiebegin: bewijs dat  geldig is
   inductieveronderstelling: neem aan dat  geldig is voor een getal 
   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.
   inductiebegin: bewijs dat  geldig is
   inductieveronderstelling: neem aan dat  geldig is voor alle  met 
   inductiestap: bewijs dat uit de inductieveronderstelling volgt dat  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 , 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, dat niet van inductie gebruikmaakt.
  
  Voorbeeld 2 
  Ieder positieve gehele getal , waarbij , is door een priemgetal te delen.
  
  Het bewijs gaat met de sterke inductie naar .
  
   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 
  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  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 .
  
  Logica
  Wiskundige terminologie