Matemaattinen induktio
Wikipedia
Matemaattinen induktio on matemaattinen todistus, joka kuuluu matemaattisen algebran päähaaraan.
Matemaattinen induktio perustuu induktioperiaatteeseen, jolla todistetaan luonnollista lukua n koskeva väite todeksi kaikilla n:n arvoilla, esim. 1 + 2 + 3 + ... + n = n(n + 1) / 2. Tämä perustuu siihen, että jos joukolle A pätee
- 1)
ja - 2) Ehdosta
,
niin 
.
Matemaattinen induktio koostuu kolmesta vaiheesta:
1. Perusaskel
- Osoitetaan, että P(0) on tosi
2. Induktioaskel
- Induktio-oletus: P(n) on tosi arvolla n = k
- Induktioväite: P(n) tosi arvolla n = k + 1
- Todistus: todistetaan, että oletuksesta seuraa väitös
3. Johtopäätös
- Induktioaskeleessa todistettiin, että P(n) on tosi aina seuraavalla n:n arvolla. Tämän induktioperiaatteen mukaan P(n) on tosi kaikilla n:n luonnollisilla arvoilla.
