Matematická indukce je základní metoda dokazování v matematice, určená zejména pro tvrzení formulovaná pro všechna přirozená čísla. Intuitivně ji lze chápat jako řetězovou reakci: pokud je tvrzení pravdivé pro první případ a z pravdivosti libovolného případu vyplývá pravdivost případu následujícího, pak je pravdivé pro všechny případy. Tuto myšlenku lze formalizovat v několika krocích níže.

Princip

  • Základní krok (base case): prokážeme, že tvrzení platí pro první prvek (např. pro n = 1).
  • Indukční krok (induction step): předpokládáme, že tvrzení platí pro nějaké pevné, ale libovolné n = n0 (tzv. indukční předpoklad) a pak ukážeme, že z tohoto předpokladu plyne, že tvrzení platí i pro n = n0 + 1.
  • Pokud jsou oba kroky splněny, pak tvrzení platí pro všechna přirozená čísla (resp. pro všechna n větší nebo rovna bazickému případu).

Formální jazyk

  • Uveďte, že důkaz bude proveden indukcí nad n {\displayystyle n}
  • Ukažte, že tvrzení je pravdivé, když n je 1 (základní krok).
  • Předpokládejte, že tvrzení je pravdivé pro libovolné přirozené číslo n — tomu se říká indukční předpoklad.
  • Ukažte, že z tohoto předpokladu plyne pravdivost tvrzení i pro {\displaystyle n+1} (indukční krok).

Protože platí pro 1, pak podle indukčního kroku platí i pro 2, poté pro 3, atd. — tedy pro všechna přirozená čísla.

Příklad: součet prvních n přirozených čísel

Dokažme vzorec pro součet prvních n přirozených čísel:

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)}

Výrok přepíšeme ve tvaru součtu:

∑_{k=1}^{n} k = {\tfrac{1}{2}} n(n+1) — což lze ekvivalentně zapsat i jako

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

Důkaz indukcí na n:

Základní krok (n = 1):

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

Tvrzení platí pro n = 1.

Indukční krok: Nechť tvrzení platí pro nějaké pevné n = n0, tj. předpokládejme indukční předpoklad

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

Musíme ukázat, že pak tvrzení platí i pro n = n0 + 1. Platí

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

Dosadíme indukční předpoklad:

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

Tedy platí

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

tedy vzorec platí i pro n = n0 + 1. Indukční krok je dokončen a důkaz je správný.

Alternativní vysvětlení (párování)

Pro ilustraci lze součet 1 + 2 + ... + n také odvodit párováním členů: když sečteme první a poslední člen, druhý a předposlední atd., vznikne n/2 párů (pro sudé n) každého součtu n+1, takže součet je (n/2)(n+1). Pro liché n zůstane uprostřed prostřední člen (n+1)/2 a celkový výsledek je stejný: n(n+1)/2.

Poznámky a časté chyby

  • Indukce neznamená pouze opakování mechanického postupu; klíčová je správná formulace indukčního předpokladu a přesné odvození kroku n0 → n0+1.
  • Je-li základní případ jiné než n = 1 (např. n = 0 nebo n = 5), je třeba ho explicitně uvést a indukci provádět od něj dál. Indukce garantuje pravdivost pouze od zvoleného bazického případu výše.
  • Existuje i silná (úplná) indukce, kde v indukčním kroku předpokládáme pravdivost tvrzení pro všechna menší čísla než n0 a z toho odvozujeme pravdivost pro n0; tato varianta je užitečná například při důkazech o prvočíselných faktorizacích nebo rekurentních vazbách.

Matematická indukce je velmi užitečný nástroj — po osvojení si principu a častých triků (volba správného indukčního předpokladu, úprava algebraických výrazů) se stává přirozenou součástí pracovního arzenálu při formálním dokazování.