Matematická indukcia je štandardná technika dokazovania tvrdení, ktoré majú zmysel pre všetky prirodzené čísla. Používa sa vždy, keď chceme ukázať, že nejaké vlastnosti alebo vzťahy platia pre každé prirodzené číslo. Myšlienka je jednoduchá: stačí overiť prvý prípad a potom dokázať, že ak vlastnosť platí pre ľubovoľné n, tak platí aj pre n+1. Potom, opakovaním tohto kroku, dôjdeme k tomu, že platí pre všetky ďalšie čísla.

Základný princíp (krok po kroku)

  • Základný prípad (base case): Ukážeme, že tvrdenie platí pre prvé prirodzené číslo (zvyčajne n = 1, niekedy n = 0 alebo iné začiatkové n).
  • Indukčný predpoklad (induction hypothesis): Predpokladáme, že tvrdenie platí pre nejaké ľubovoľné, ale pevné n (označme ho n0).
  • Indukčný krok (inductive step): Ukážeme, že z platnosti pre n0 plynie platnosť pre n0 + 1.

Ak sú splnené oba kroky, potom tvrdenie platí pre všetky hodnoty n od začiatočného bodu ďalej (pretože z 1 vyplýva 2, z 2 vyplýva 3, atď.).

Varianty a poznámky

  • Sílna (úplná) indukcia: Pri tomto variante v indučnom kroku predpokladáme platnosť tvrdenia pre všetky menšie hodnoty (1,2,...,n0) a z toho odvodíme platnosť pre n0+1. Tento variant je ekvivalentný s obyčajnou indukciou, ale často jednoduchší pri dôkazoch, kde n0+1 závisí od viacerých menších hodnôt než len od n0.
  • Dôležité: Indukčný krok musí byť dokázaný pre všeobecné n (nie len pre konkrétne n0), t. j. dôkaz má byť platný pre ľubovoľné n0, za ktoré predpoklad platí.
  • Začiatočný index: Indukcia môže začínať na inom čísle než 1 (napr. n=0 alebo n=5) podľa toho, kde má tvrdenie zmysel.

Ukážkový dôkaz indukciou — súčet prvých n prirodzených čísel

Ukážeme, že pre všetky prirodzené čísla n platí vzorec

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)} {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)}

Dôkaz indukciou na n:

Základný prípad: Pre n = 1 máme

2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)},

čiže súčet 1 je rovný 1·(1+1)/2 = 1, takže základný prípad platí.

Indukčný predpoklad: Predpokladajme, že pre nejaké n = n0 platí

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)} {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)}

Indukčný krok: Potrebujeme ukázať, že potom platí aj pre n = n0 + 1. Máme

2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k} {\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k}

čo môžeme prepísať ako

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)} {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)}

Podľa indukčného predpokladu nahradíme 2∑_{k=1}^{n0}k výrazom n0(n0+1):

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)}

Po vydelení dvoma dostaneme

∑_{k=1}^{n_{0}+1}k={\tfrac{1}{2}}(n_{0}+1)(n_{0}+2)

teda platnosť pre n0+1 je dokázaná. To uzatvára indukčný krok.

Záver: Základný prípad a indukčný krok spolu zabezpečujú, že vzorec platí pre všetky prirodzené čísla n.

Praktické tipy a bežné omyly

  • Uistite sa, že základný prípad skutočne začína tam, kde má tvrdenie zmysel (niekedy to nie je n = 1).
  • Pri indukčnom kroku formulujte jasne, čo predpokladáte (pre ktoré n) a čo treba dokázať (pre n+1 alebo pre n0+1).
  • Nepoužívajte indukčný predpoklad pre n+1 (to by bolo kruhové dokazovanie). Predpoklad sa vzťahuje len na n0, nie na n0+1.
  • Silná indukcia je užitočná, keď treba v kroku použiť platnosť pre viacero menších hodnôt než len pre n0.

Matematická indukcia je veľmi všestranný nástroj: používa sa pri dôkazoch vzorcov, nerovností, vlastností deliteľnosti, rekurentných definícií a v mnohých ďalších situáciách. S praxou sa naučíte rozpoznať prípady, kde je indukcia najjednoduchším riešením.