Vaak bestaat een probleem erin aan te tonen dat een bepaalde eigenschap geldt voor elk natuurlijk getal. Hiervoor gebruiken we het principe van de volledige inductie
- Basisstap: Men bewijst
- Inductiehypothese: Men bewijst voor elke
dat als
geldt, dan ook
geldt.
Er bestaat ook een andere vorm, die we de sterke inductie noemen:
Voor elk natuurlijk getal
geldt :
- De geldigheid van de formule voor
is duidelijk, want
. Dit is de basisstap.
- De inductiehypothese : stel dat de formule ook geldt voor
. Dan is:
en dit is precies de formule voor