Ero sivun ”Matemaattinen induktio” versioiden välillä
[arvioimaton versio] | [arvioimaton versio] |
p typo |
no laitetaan tänne sitten |
||
Rivi 3: | Rivi 3: | ||
'''Matemaattinen induktio''' on [[matemaattinen todistus]]menetelmä, joka kuuluu matemaattisen [[algebra]]n päähaaraan. |
'''Matemaattinen induktio''' on [[matemaattinen todistus]]menetelmä, joka kuuluu matemaattisen [[algebra]]n päähaaraan. |
||
Toisin kuin [[Induktiivinen päättely|induktiivisessa päättelyssä]], matemaattiseen induktioon ei sisälly [[Induktion ongelma|Humen ongelmaa]], sillä matemaattinen induktio on [[rekursio]]on perustuvaa todistamista eli pätevää [[deduktiivinen päättely|deduktiivista päättelyä]]. Todistus perustuu rekursiorelaation avulla määriteltyyn äärettömän joukon säännönmukaisuuteen, joka todistuksessa yleistetään koko joukkoon, esimerkiksi [[luonnolliset luvut|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.<ref name=cog121/><ref name=vtt/> |
Toisin kuin [[Induktiivinen päättely|induktiivisessa päättelyssä]], matemaattiseen induktioon ei sisälly [[Induktion ongelma|Humen ongelmaa]], sillä matemaattinen induktio on [[rekursio]]on perustuvaa todistamista eli pätevää [[deduktiivinen päättely|deduktiivista päättelyä]].{{selvennä}} Todistus perustuu rekursiorelaation avulla määriteltyyn äärettömän joukon säännönmukaisuuteen, joka todistuksessa yleistetään koko joukkoon, esimerkiksi [[luonnolliset luvut|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.<ref name=cog121/><ref name=vtt/> |
||
Matemaattinen induktio perustuu ''induktioperiaatteeseen'', jolla todistetaan luonnollista lukua <math>n</math> koskeva väite todeksi kaikilla <math>n</math>:n arvoilla. Teknisesti induktiotodistus koostuu kolmesta vaiheesta: |
Matemaattinen induktio perustuu ''induktioperiaatteeseen'', jolla todistetaan luonnollista lukua <math>n</math> koskeva väite todeksi kaikilla <math>n</math>:n arvoilla. Teknisesti induktiotodistus koostuu kolmesta vaiheesta: |
Versio 3. syyskuuta 2010 kello 13.01
Matemaattinen induktio on matemaattinen todistusmenetelmä, joka kuuluu matemaattisen algebran päähaaraan.
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ä.selvennä 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]
Matemaattinen induktio perustuu induktioperiaatteeseen, jolla todistetaan luonnollista lukua koskeva väite todeksi kaikilla :n 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 :n arvolla. Koska on tosi, niin myös on tosi kaikilla :n luonnollisilla arvoilla.
Esimerkki
Todistetaan oikeaksi kaava .
- Perusaskel:
- Näytetään, että P(0) pätee:
- 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
- .
- Induktio-oletuksen nojalla voidaan tehdä sijoitus , jolla yhtälön vasen puoli saadaan muotoon
- .
- Jos tämä voidaan esittää muodossa , on induktiotodistus saatettu loppuun.
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 .
Katso myös
- Induktiivinen päättely - yksittäisestä yleiseen
- Deduktiivinen päättely - yleisestä yksittäiseen