Matematická indukcia

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:

0+1+2+3+\cdots +n={\frac {n(n+1)}{2}}

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

0+1+2+\cdots +m={\frac {m(m+1)}{2}}

Pridaním m + 1 k obidvom stranám rovnice dostaneme

1+2+\cdots +m+(m+1)={\frac {m(m+1)}{2}}+(m+1)

čo sa rovná

={\frac {m(m+1)}{2}}+{\frac {2(m+1)}{2}}={\frac {(m+2)(m+1)}{2}}

a máme teda

1+2+\cdots +(m+1)={\frac {(m+1)((m+1)+1)}{2}}

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^[1]. 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 $n=1$ 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 $n$ koní a chceme ho dokázať pre $n+1$ koní. Kone si očíslujeme $1,2,3,...,n+1$ , kde farba i-teho koňa je $f_{i}$ . Pozrieme sa na farbu prvých $n$ koní $f_{1},f_{2},...,f_{n}$ . Podľa indukčného predpokladu môžeme usúdiť, že sú všetky rovnakej farby. Teraz sa pozrieme na farbu koní $f_{2},f_{3},f_{4},...,f_{n+1}$ . Tých koní je $n$ , takže znova použijeme indukčný predpoklad a môžeme povedať, že aj tie sú všetky rovnakej farby. Keďže vieme, že $f_{1}=f_{2}=f_{3}...=f_{n}$ a zároveň aj $f_{2}=f_{3}=f_{4}=...=f_{n+1}$ , môžeme povedať, že $f_{1}=f_{n+1}$ . Teraz sme dokázali, že ak výrok platí pre $n$ tak platí pre $n+1$ .