Důkaz matematickou indukcí
Příklad.
Dokažte, že pro každé přirozené číslo \(n\) platí
\[
1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}. \tag{P(n)}
\]
Řešení.
Jak lze zavést přirozená čísla axiomaticky pomocí tzv. Peanových axiómů, se můžete
dočíst
zde.
Další informace o matematické indukci naleznete zde.
Pro \(n = 1\) máme \[ 1 = \frac{1(1+1)}{2} \implies P(1) \text{ platí}. \] (Obecný krok matematické indukce). Předpokládejme, že platí \(P(n)\) pro nějaké pevné \(n \in \mathbb{N}\). Ukažme, že pak platí též \(P(n+1)\). Máme \begin{align*} 1 + 2 + 3 + \ldots + n + (n+1) &= \frac{n(n+1)}{2} + (n+1) \\ &= \frac{n(n+1) + 2(n+1)}{2} \\ &= \frac{(n+1)(n+2)}{2}. \end{align*} Tedy \(P(n+1)\) platí. Podle principu matematické indukce tedy platí \(P(n)\) pro všechna \(n \in \mathbb{N}\).