Matematická indukcia je metóda dokazovania matematických viet a tvrdení, ktorá sa používa, ak chceme ukázať, ž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.
Príklad
Majme nasledujúce tvrdenie:
pre všetky prirodzené čísla n. Dôkaz pravdivosti tohto tvrdenia je uvedený v nasledujúcej podkapitole.
Dôkaz
Báza:
Najskôr skontrolujeme, či toto 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.
Indukčný krok:
Teraz chceme ukázať, že pokiaľ toto 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 ...
Všetky kone majú rovnakú farbu
Všetky kone majú rovnakú farbu je paradox, ktorý vznikne z nesprávneho použitia matematickej indukcie. Bol predstavený maďarským matematikom George Pólya. Ukazuje na chyby, čo môžu nastať pri dôkazoch matematickou indukciou.
Argument
Chceme dokázať, že všetky kone majú rovnakú farbu.
Báza:
Pre to zjavne platí. Ak máme v skupine jedného koňa, tak má celá skupina rovnakú farbu a to farbu toho jedného koňa.
Indukčný krok:
Predpokladáme, že výrok platí pre koní a chceme ho dokázať pre koní. Kone si očíslujeme , kde farba i-teho koňa je . Pozrieme sa na farbu prvých koní . Podľa indukčného predpokladu môžeme usúdiť, že sú všetky rovnakej farby. Teraz sa pozrieme na farbu koní . Tých koní je , takže znova použijeme indukčný predpoklad a môžeme povedať, že aj tie sú všetky rovnakej farby. Keďže vieme, že a zároveň aj , môžeme povedať, že . Teraz sme dokázali, že ak výrok platí pre tak platí pre .
Výrok platí pre .
Výrok platí pre všetky kladné celé čísla.
Každá podmnožina koní má navzájom rovnakú farbu.
Koní je konečný počet.
Všetky kone majú rovnakú farbu.
Vysvetlenie
V indukčnom kroku (od do ) sa predpokladá, že . Indukcia by platila iba keby bola báza dokázaná pre .
Referencie
Iné projekty
Externé odkazy Dôkaz matematickou indukciou na pohodovamatematika.sk
Kategória:Matematická logika