Matematická indukcia

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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:

  1. Báza: Ukážeme, že tvrdenie platí pre najmenšie číslo z postupnosti.
  2. 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:

  1. Spadne prvá kocka domina
  2. Ak spadne nejaká kocka domina, spadne aj jej najbližší sused.

Výsledkom potom je, že spadnú všetky kocky.

Príklad[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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.

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

  1. Platí pre 0.
  2. Ak platí pre 0, platí aj pre 1
  3. Ak platí pre 1, platí aj pre 2
  4. Ak platí pre 2, platí aj pre 3
  5. ...