Bewijs door inductie

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 P(1)
  • Inductiehypothese: Men bewijst voor elke k dat als P(k) geldt, dan ook P(k+1) geldt.

Er bestaat ook een andere vorm, die we de sterke inductie noemen:

  • Basisstap: Men bewijst P(1) .
  • Inductiehypothese: Men bewijst voor elke k dat als P(1),P(2),\ldots,P(k) gelden, dan ook P(k+1) geldt.

Voor elk natuurlijk getal n geldt :

    \[1^2+2^2+\ldots+n^2=\frac{1}{6}n(n+1)(2n+1)\]

  • De geldigheid van de formule voor n=1 is duidelijk, want  1^2=\frac{1}{6}.1.(1+1)(2+1). Dit is de basisstap.
  • De inductiehypothese : stel dat de formule ook geldt voor n=k. Dan is: 

        \begin{align*}1^2+2^2+\ldots+k^2+(k+1)^2=&(1^2+2^2+\ldots+k^2)+(k+1)^2\\=& \frac{1}{6}k(k+1)(2k+1)+(k+1)^2\\=&\frac{1}{6}(k+1)(2k^2+7k+6)\\=&\frac{1}{6}(k+1)(k+2)(2k+3) \end{align*}

    en dit is precies de formule voor n=k+1