Inductiebewijs

Waar gaat het over?

De bewijsmethode van de volledige inductie wordt wel het dominoprincipe genoemd. Hij werkt als het gaat om een stelling die moet gelden voor alle elementen van een aftelbare verzameling, bijvoorbeeld voor alle natuurlijke getallen. Je bewijst dat de stelling voor het eerste element geldt en vervolgens (de inductiestap) als hij voor een element geldt, dat hij dan ook voor zijn opvolger geldt.

Hoe werkt het?

Bewijs dat `1+2+3+...+n` gelijk is aan: `1/2n(n+1)`.

• voor `n=1` geldt: `1=1/2*1*(1+1)` (Klopt.)
• inductiestap: als dit geldt voor `n` dan ook voor `n+1`, dus uit `1+2+...+ n=1/2n(n+1)` volgt `1+2+...+n+(n+1)=1/2(n+1)(n+2)`. (Ga zelf na dat dit klopt.)

Wie en wanneer?

Een beroemd verhaal is dat van C.F. Gauss (1777 - 1855) die als zevenjarige zijn onderwijzer verbaasde door de getallen `1` t/m `100` op te tellen door in de gaten te hebben dat de uitkomst precies de helft van `100*101` is. Dit is een bijzonder geval van de stelling die hiernaast m.b.v. volledige inductie is bewezen.

Het principe van de volledige inductie berust op Peano's axioma's voor de natuurlijke getallen. Deze axioma's vormen de grondslag van de rekenkunde en zijn bedacht door de Italiaanse wiskundige G. Peano (1858-1932) die daarmee de getallentheorie formeel wilde opbouwen vanuit de verzamelingenleer.