Otvoriť hlavné menu

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:

  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íkladUpraviť

Majme nasledujúce tvrdenie:

 

pre všetky prirodzené čísla n. Dôkaz pravdivosti tohto tvrdenia je uvedený v nasledujúcej podkapitole.

DôkazUpraviť

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

  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. ...

Všetky kone majú rovnakú farbuUpraviť

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.

ArgumentUpraviť

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.

VysvetlenieUpraviť

V indukčnom kroku (od   do  ) sa predpokladá, že  . Indukcia by platila iba keby bola báza dokázaná pre  .

ReferencieUpraviť

  1. PÓLYA, George. Induction and Analogy in Mathematics. [s.l.] : [s.n.], 1954.

Externé odkazyUpraviť