Matemaattinen induktio

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

Induktiotodistuksen periaatetta voi verrata kaatuviin dominopalikoihin.

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

Perusaskel
- Osoitetaan esimerkin kautta, että $P(0)$ on tosi
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
Johtopäätös
- Induktioaskeleessa todistettiin, että $P(n)$ on tosi aina seuraavalla luvun $n$ arvolla. Koska $P(0)$ on tosi, niin myös $P(n)$ on tosi kaikilla luonnollisilla luvuilla $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]

Esimerkki

Todistetaan oikeaksi kaava

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

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

$0={\frac {0\cdot (0+1)}{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)={\frac {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ää samassa muodossa kuin induktioväitteen oikea puoli, niin induktiotodistus on saatettu loppuun. Induktioväite on tosi, koska

${\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}}.\end{aligned}}$
Johtopäätös:
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} .\qquad \Box$

Katso myös

Induktiivinen päättely (yksittäisestä tapauksesta yleiseen tapaukseen)
Deduktiivinen päättely (yleisestä tapauksesta yksittäiseen tapaukseen)

Lähteet

Looginen Päättely & Hyvä argumentaatio^{[vanhentunut linkki]}
Aarne Mämmelä (toim.) 2006. Vocabulary of a doctoral student (Arkistoitu – Internet Archive)

Kirjallisuutta

Merikoski, Jorma; Virtanen, Ari; Koivisto, Pertti: Diskreetti matematiikka I. Tampere: Tampereen yliopisto, 2001 (1993). ISBN 951-44-3604-0.
Rikkonen, Harri: Matematiikan pitkä peruskurssi II: Reaalimuuttujan funktioiden differentiaalilasku. Helsinki: Otakustantamo, 1969. ISBN 951-671-022-0.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[cog121-1] Looginen Päättely & Hyvä argumentaatio^{[vanhentunut linkki]}

[vtt-2] Aarne Mämmelä (toim.) 2006. Vocabulary of a doctoral student (Arkistoitu – Internet Archive)