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*&nbsp;=&nbsp;*m*, ***tak*** platí aj pre *n*&nbsp;=&nbsp;*m*&nbsp;+&nbsp;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. 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.

Výrok platí pre n =1.

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 n do n+1) sa predpokladá, že n \ge 2. Indukcia by platila iba keby bola báza dokázaná pre n \ge 2.

## Referencie

## Externé odkazy
* Dôkaz matematickou indukciou na  pohodovamatematika.sk 

Kategória:Matematická logika