Matemaattinen induktio

Induktiotodistuksen periaatetta voi verrata kaatuviin dominopalikkoihin

Matemaattinen induktio on matemaattinen todistus, joka kuuluu matemaattisen algebran päähaaraan.

Matemaattinen induktio perustuu induktioperiaatteeseen, jolla todistetaan luonnollista lukua $n$ koskeva väite todeksi kaikilla $n$:n arvoilla, esimerkiksi $0+1+2+\dots +n={\frac {n(n+1)}{2}}$. Tämä perustuu siihen, että jos joukolle A pätee

1) $0\in A$ ja

2) Ehdosta $n\in A\Rightarrow n+1\in A$,

niin $A=\mathbb {N}$.

Matemaattinen induktio koostuu kolmesta vaiheesta:

1. Perusaskel
   • Osoitetaan, että $P(0)$ on tosi
2. Induktioaskel
   • Induktio-oletus: $P(n)$ on tosi arvolla $n=k$
   • Induktioväite: $P(n)$ tosi arvolla $n=k+1$
   • Todistus: todistetaan, että oletuksesta seuraa väitös
3. Johtopäätös
   • Induktioaskeleessa todistettiin, että $P(n)$ on tosi aina seuraavalla $n$:n arvolla.
   • Tämän induktioperiaatteen mukaan $P(n)$ on tosi kaikilla $n$:n luonnollisilla arvoilla.

Esimerkki

Todistetaan esimerkissä kaava $0+1+2+\dots +n={\frac {n(n+1)}{2}}$.

1. Perusaskel:

   Todistetaan, että P(0) pätee:

   $0={\frac {0\cdot (0+1)}{2}}$

2. Induktioaskel:

   Induktio-oletus: P(n) on tosi. (Varmaksi tiedetään jo P(0) paikkansapitävyys).

   Induktioväite: P(n + 1) on tosi.

   $0+1+2+\dots +n+(n+1)={\frac {(n+1)\cdot ((n+1)+1)}{2}}$

   Koska yllä todettiin jo, että kaava pätee arvolla n = 0, voidaan tehdä sijoitus $(0+1+2+\dots +n)=n(n+1)/2$.

   ${\frac {n\cdot (n+1)}{2}}+(n+1)={\frac {(n+1)\cdot ((n+1)+1)}{2}}$

   Jos yhtälön vasen puoli voidaan esittää muodossa ${\frac {(n+1)\cdot ((n+1)+1)}{2}}\$, on induktiotodistus saatettu loppuun.

   ${\begin{aligned}{\frac {n\cdot (n+1)}{2}}+(n+1)&=(n+1)\left({\frac {n}{2}}+1\right)\\&=(n+1)\left({\frac {n}{2}}+{\frac {2}{2}}\right)\\&={\frac {(n+1)(n+2)}{2}}\\&={\frac {(n+1)\cdot ((n+1)+1)}{2}}\\&&\Box \end{aligned}}$

Tästä siis seuraa, että kaava pätee arvolla n + 1. Kaavan todettiin alussa pitävän paikkansa, kun n = 0. Tästä seuraa, että kaava on tosi myös arvolla n = 0 + 1. Seurauksena taas tästä kaava pitää myös paikkansa arvoilla $n\in \{0,\ (0+1),\ (0+1)+1,\ \dots \}$