Volledige inductie
Uit Wikipedia, de vrije encyclopedia
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.