Matemaattinen induktio

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

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

 Perusaskel
 Osoitetaan esimerkin kautta, että  on tosi
 Induktioaskel
 Induktio-oletus: oletetaan, että  on tosi arvolla 
 Induktioväite: väitetään, että  tosi arvolla 
 Todistus: todistetaan, että induktio-oletuksesta seuraa induktioväite
 Johtopäätös
 Induktioaskeleessa todistettiin, että  on tosi aina seuraavalla luvun  arvolla. Koska  on tosi, niin myös  on tosi kaikilla luonnollisilla luvuilla .

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.

Esimerkki
Todistetaan oikeaksi kaava

 Perusaskel: 
 Näytetään, että  pätee:
 
 Induktioaskel: 
Induktio-oletus:  on tosi. (Varmaksi tiedetään jo siis  paikkansapitävyys.)
 Induktioväite:  on tosi. Toisin sanoen
 
 Induktio-oletuksen nojalla voidaan tehdä sijoitus , jolla yhtälön vasen puoli saadaan muotoon
 
 Jos tämä voidaan esittää samassa muodossa kuin induktioväitteen oikea puoli, niin induktiotodistus on saatettu loppuun. Induktioväite on tosi, koska
 
 Johtopäätös: 
 Tästä siis seuraa, että kaava pätee arvolla . Kaavan todettiin alussa pitävän paikkansa, kun . Näiden kahden seurauksena kaava pitää paikkansa myös arvoilla

Katso myös
Induktiivinen päättely (yksittäisestä tapauksesta yleiseen tapaukseen)
Deduktiivinen päättely (yleisestä tapauksesta yksittäiseen tapaukseen)

Lähteet

Kirjallisuutta 
 
 

Algebra
Matemaattinen logiikka
Seulonnan keskeiset artikkelit