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 



Luokka:Algebra
Luokka:Matemaattinen logiikka
Luokka:Seulonnan keskeiset artikkelit