Matemaattinen induktio

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

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

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

Toisin kuin induktiivisessa päättelyssä, matemaattiseen induktioon ei sisälly Humen ongelmaa, sillä matemaattinen induktio on rekursioon perustuvaa todistamista eli pätevää deduktiivista päättelyä. Todistus perustuu rekursiorelaation avulla määriteltyyn äärettömän joukon säännönmukaisuuteen, joka todistuksessa yleistetään koko joukkoon, esimerkiksi luonnollisten lukujen joukkoon. Matemaattinen induktio voidaan myös samaistaa täydellisen induktion kanssa, sillä siinä käydään rekursiivisesti kaikki mahdolliset yksittäistapaukset läpi.^[1][2]

1. ↑ Viittausvirhe: Virheellinen <ref>-elementti; viitettä cog121 ei löytynyt
2. ↑ Viittausvirhe: Virheellinen <ref>-elementti; viitettä vtt ei löytynyt