Matematická indukcia
Z Wikipédie
Matematická indukcia je metóda dokazovania matematických viet a tvrdení, ktorá sa používa, ak chceme ukázat, že dané tvrdenie platí pre všetky prirodzené čísla, prípadne inú, dopredu danú nekonečnú postupnosť.
Typický dôkaz indukciou sa skladá z dvoch krokov:
- Báza: Ukážeme, že tvrdenie platí pre najmenšie číslo z postupnosti.
- Indukčný krok: Ukážeme, že ak tvrdenie platí pre n = m, tak platí aj pre n = m + 1 (Časť nasledujúca bezprostredne po ak sa niekedy nazýva indukčný predpoklad).
Tento postup sa niekedy prirovnáva k dominu. Obidve tieto časti sú totiž podobné dominovému efektu:
- Spadne prvá kocka domina
- Ak spadne nejaká kocka domina, spadne aj jej najbližší sused.
Výsledkom potom je, že spadnú všetky kocky.
[úprava] Príklad
Majme nasledujúce tvrdenie:
pre všetky prirodzené čísla n. Dôkaz pravdivosti tohto tvrdenia je uvedený v nasledujúcej podkapitole.
[úprava] Dôkaz
Najskôr skontrolujeme, či tvrdenie platí pre n = 0. Zrejme áno, pretože súčet prvých 0 prirodzených čísel je 0 a 0(0 + 1)/2=0.
Teraz chceme ukázať, že pokiaľ tvrdenie platí pre n = m, platí aj pre n = m + 1.
Predpokladajme teda, že pre n = m tvrdenie platí, čiže
Pridaním m + 1 k obidvom stranám rovnice dostaneme
čo sa rovná
a máme teda
Toto je tvrdenie pre n = m + 1. Dokázali sme, že je pravdivé, pokiaľ je pravdivé tvrdenie pre n = m.
Tvrdenie teda platí pre všetky prirodzené čísla, pretože
- Platí pre 0.
- Ak platí pre 0, platí aj pre 1
- Ak platí pre 1, platí aj pre 2
- Ak platí pre 2, platí aj pre 3
- ...