Ero sivun ”Matemaattinen induktio” versioiden välillä
Siirry navigaatioon
Siirry hakuun
[arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
Ei muokkausyhteenvetoa |
|||
Rivi 1: | Rivi 1: | ||
[[Kuva:Dominoeffect.png|right|thumb|240px|Induktiotodistuksen periaatetta voi verrata kaatuviin dominopalikkoihin]] |
[[Kuva:Dominoeffect.png|right|thumb|240px|Induktiotodistuksen periaatetta voi verrata kaatuviin dominopalikkoihin]] |
||
'''Matemaattinen induktio''' on matemaattinen todistus, joka kuuluu matemaattisen [[algebra]]n päähaaraan. |
'''Matemaattinen induktio''' on [[matemaattinen todistus]]menetelmä, joka kuuluu matemaattisen [[algebra]]n päähaaraan. |
||
Matemaattinen induktio perustuu induktioperiaatteeseen, jolla todistetaan luonnollista lukua <math>n</math> koskeva väite todeksi kaikilla <math>n</math>:n arvoilla |
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: |
||
Tämä perustuu siihen, että jos joukolle ''A'' pätee |
|||
:1) <math>0 \in A</math> ja |
|||
:2) Ehdosta <math>n \in A \Rightarrow n+1 \in A</math>, |
|||
niin <math>A=\mathbb{N}</math>. |
|||
⚫ | |||
Matemaattinen induktio koostuu kolmesta vaiheesta: |
|||
⚫ | |||
⚫ | |||
⚫ | |||
# Induktioaskel |
# Induktioaskel |
||
#* Induktio-oletus: <math>P(n)</math> on tosi arvolla <math>n=k</math> |
#* Induktio-oletus: oletetaan, että <math>P(n)</math> on tosi arvolla <math>n=k</math> |
||
#* Induktioväite: <math>P(n)</math> tosi arvolla <math>n=k+1</math> |
#* Induktioväite: väitetään, että <math>P(n)</math> tosi arvolla <math>n=k+1</math> |
||
#* Todistus: todistetaan, että oletuksesta seuraa |
#* Todistus: todistetaan, että induktio-oletuksesta seuraa induktioväite |
||
# Johtopäätös |
# Johtopäätös |
||
#* Induktioaskeleessa todistettiin, että <math>P(n)</math> on tosi aina seuraavalla <math>n</math>:n arvolla. |
#* Induktioaskeleessa todistettiin, että <math>P(n)</math> on tosi aina seuraavalla <math>n</math>:n arvolla. Koska <math>P(0)</math> on tosi, niin myös <math>P(n)</math> on tosi kaikilla <math>n</math>:n luonnollisilla arvoilla. |
||
#* Tämän induktioperiaatteen mukaan <math>P(n)</math> on tosi kaikilla <math>n</math>:n luonnollisilla arvoilla. |
|||
==Esimerkki== |
==Esimerkki== |
||
Todistetaan |
Todistetaan oikeaksi kaava <math>0+1+2+ \dots +n=\frac{n(n+1)}{2}</math>. |
||
# '''Perusaskel:''' |
# '''Perusaskel:''' |
||
#: |
#: Näytetään, että ''P(0)'' pätee: |
||
#: <math>0 = \frac{0 \cdot (0+1)}{2}</math> |
#: <math>0 = \frac{0 \cdot (0+1)}{2}</math> |
||
# '''Induktioaskel:''' |
# '''Induktioaskel:''' |
||
#: ''Induktio-oletus: P(n)'' on tosi. ''(Varmaksi tiedetään jo P(0) paikkansapitävyys)''. |
#: ''Induktio-oletus: P(n)'' on tosi. ''(Varmaksi tiedetään jo siis P(0) paikkansapitävyys)''. |
||
#: ''Induktioväite: P(n + 1)'' on tosi. Toisin sanoen |
#: ''Induktioväite: P(n + 1)'' on tosi. Toisin sanoen |
||
#: <math>0+1+2+ \dots +n+(n+1) = \frac{(n+1) \cdot ((n + 1)+1)}{2}</math>. |
#: <math>0+1+2+ \dots +n+(n+1) = \frac{(n+1) \cdot ((n + 1)+1)}{2}</math>. |
Versio 10. joulukuuta 2009 kello 22.11
Matemaattinen induktio on matemaattinen todistusmenetelmä, joka kuuluu matemaattisen algebran päähaaraan.
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 .