Matemaattinen induktio

Induktiotodistuksen periaatetta voi verrata kaatuviin dominopalikkoihin

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

Matemaattinen induktio perustuu induktioperiaatteeseen, jolla todistetaan luonnollista lukua $n$ koskeva väite todeksi kaikilla $n$:n arvoilla. Teknisesti induktiotodistus koostuu kolmesta vaiheesta:

1. Perusaskel
   • Osoitetaan esimerkin kautta, että $P(0)$ on tosi
2. Induktioaskel
   • Induktio-oletus: oletetaan, että $P(n)$ on tosi arvolla $n=k$
   • Induktioväite: väitetään, että $P(n)$ tosi arvolla $n=k+1$
   • Todistus: todistetaan, että induktio-oletuksesta seuraa induktioväite
3. Johtopäätös
   • Induktioaskeleessa todistettiin, että $P(n)$ on tosi aina seuraavalla $n$:n arvolla. Koska $P(0)$ on tosi, niin myös $P(n)$ on tosi kaikilla $n$:n luonnollisilla arvoilla.

Esimerkki

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

1. Perusaskel:

   Näytetään, että P(0) pätee:

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

2. Induktioaskel:

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

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

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

   Induktio-oletuksen nojalla voidaan tehdä sijoitus $(0+1+2+\dots +n)=n(n+1)/2$, jolla yhtälön vasen puoli saadaan muotoon

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

   Jos tämä 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. Näiden kahden seurauksena kaava pitää paikkansa myös arvoilla $n\in \{0,\ (0+1),\ (0+1)+1,\ \dots \}=\mathbb {N}$.