Důkaz matematickou indukcí
Důkaz matematickou indukcí se používá pro věty, které se týkají (téměř) všech přirozených čísel nebo jsou na nich nějak závislé. Přesněji řečeno, používáme jej pro věty typu \(\forall (n \in \mathbb{N})\), \(n\) ≥ \(n\)\(_0\): \(\mathbf{A}\)(\(n\)), kde \(\mathbf{A}\)(\(n\)) je výrokový vzorec s volnou proměnnou \(n\) reprezentující typicky nějakou vlastnost přirozených čísel a kde \(n\)\(_0\) je nějaké konkrétní přirozené číslo, od něhož výše má daná vlastnost platit. Často má \(\mathbf{A}\)(\(n\)) platit pro každé přirozené číslo, pak je \(n\)\(_0\) = 1 a podmínku \(n\) ≥ \(n\)\(_0\) neuvádíme. Důkaz matematickou indukcí sestává ze dvou kroků:
- Dokážeme, že \(\mathbf{A}\)(\(n\)) platí pro \(n\) = \(n\)\(_0\).
- Dokážeme implikaci: \(\forall (k \in \mathbb{N})\): \(\mathbf{A}\)(\(k\)) \(\Rightarrow\) \(\mathbf{A}\)(\(k + 1\)), této části říkáme indukční krok.
Opravdu stačí tyto dva kroky k dokázání vět v uvedeném tvaru? Zkusme si situaci trochu rozebrat:
Mějme větu, která říká, že nějaká vlastnost platí pro všechna přirozená čísla (např. že 2\(\mid\)(\(n\)\(^3\) − 11\(n\))). V prvním kroku dokážeme, že tato věta platí pro číslo 1. Poté dokážeme, že pokud tato věta platí pro nějaké přirozené číslo \(k\), pak platí i pro \(k\) + 1. Víme tedy, že věta platí pro číslo 1. Díky dokázané implikaci ale také dokážeme odvodit, že platí i pro dvojku (platí-li výrok \(\mathbf{A}\) a současně \(\mathrm{\mathbf{A}}\Rightarrow \mathrm{\mathbf{B}}\), pak platí i výrok \(\mathbf{B}\)). Když víme, že platí pro dvojku, můžeme stejným způsobem odvodit, že platí i pro číslo tři, a takto bychom mohli pokračovat dále a dokázat větu pro všechna přirozená čísla. Zmiňované dva kroky tedy stačí.
Příklad 12
Dokažte: \(\forall (n \in \mathbb{N})\): 1 + 2 + … \(n\) = ½ · (\(n\) + 1) · \(n\).
Prvním krokem je ověření platnosti pro číslo 1. Dosadíme tedy toto číslo do rovnosti. Levá strana bude 1, pravá strana bude ½ · 1 · (1 + 1), což je opět 1. Pro číslo 1 tedy věta platí.
Přichází na řadu indukční krok. Předpokládejme, že tato věta platí pro nějaké přirozené číslo \(k\), tedy že pro toto \(k\) platí:
1 + 2 + … \(k\) = ½ · (\(k\) + 1) · \(k\)
Nyní musíme dokázat, že za tohoto předpokladu platí věta i pro (\(k\) + 1), tedy že platí:
1 + 2 + … \(k\) + (\(k\) + 1) = ½ · (\(k\) + 2)(\(k\) + 1).
Levá strana je 1 + 2 + … \(k\) + (\(k\) + 1). My však z našeho předpokladu víme, že 1 + 2 + … \(k\) = ½ · (\(k\) + 1) · \(k\), a tak můžeme psát:
1 + 2 + … \(k\) + (\(k\) + 1) = ½ · (\(k\) + 1) · \(k\) + (\(k\) + 1)
Modrou barvou je naznačeno, u které části výrazu došlo k aplikaci našeho předpokladu. Pokud budeme výraz dále upravovat (vytkneme závorku (\(k\) + 1)), získáme:
½ · (\(k\) + 1) · \(k\) + (\(k\) + 1) = (\(k\) + 1)(½ · \(k\) + 1) = ½ · (\(k\) + 2)(\(k\) + 1).
Dostali jsme se od levé strany dokazované rovnosti k pravé, dokázali jsme, že platí:
1 + 2 + … \(k\) + (\(k\) + 1) = ½ · (\(k\) + 2)(\(k\) + 1).
Provedli jsme oba kroky důkazu a věta je tak dokázána.
☒
Příklad 13
Dokažte: \(\forall (n \in \mathbb{N})\): 2\(\mid\)(\(n\)\(^3\) + 11\(n\)).
Pokud za \(n\) dosadíme 1, tvrzení platí. První krok je splněn.
Předpokládejme, že tvrzení platí pro nějaké přirozené číslo \(k\), tedy že 2\(\mid\)(\(k\)\(^3\) + 11\(k\)). Zkusme dokázat, že platí i pro (\(k\) + 1). Dosaďme tedy (\(k\) + 1) za \(n\) do výrazu (\(n\)\(^3\) + 11\(n\)):
(\(k\) + 1)\(^3\) + 11(\(k\) + 1) = \(k\)\(^3\) + 3\(k\)\(^2\) + 3\(k\) + 1 + 11\(k\) + 11 = \(k\)\(^3\) + 11\(k\) + 3\(k\)\(^2\) + 3\(k\) + 12
Modře označený výraz je podle našeho předpokladu dělitelný dvěma. Abychom prokázali, že i celý výraz (\(k\)\(^3\) + 11\(k\) + 3\(k\)\(^2\) + 3\(k\) + 12) je dělitelný dvěma, zbývá dokázat, že (3\(k\)\(^2\) + 3\(k\) + 12) je také dělitelné dvěma. Můžeme výraz ještě upravit: 3(\(k\)\(^2\) + \(k\) + 4). Číslo tři není dělitelné dvěma, musíme tedy dokázat, že číslo dvě dělí číslo (\(k\)\(^2\) + \(k\) + 4).
Je-li \(k\) sudé, jeho druhá mocnina bude také sudé číslo, takže výraz (\(k\)\(^2\) + \(k\) + 4) bude součtem tří sudých čísel, což je opět číslo sudé, a tedy dělitelné dvěma. Je-li \(k\) liché, pak jeho druhá mocnina je také liché číslo. Náš výraz tak bude součtem dvou lichých čísel (která dohromady dají číslo sudé) a jednoho čísla sudého, což je dohromady opět číslo sudé. (\(k\)\(^2\) + \(k\) + 4) je tedy jistě sudé číslo, číslo dvě dělí (\(k\)\(^3\) + 11\(k\) + 3\(k\)\(^2\) + 3\(k\) + 12). Vztah platí i pro (\(k\) + 1), věta je dokázána.
☒
Příklad 14
Dokažte: \(\forall (n \in \mathbb{N})\): 6\(\mid\)(\(n\)\(^3\) + 5\(n\)).
Pokud za \(n\) dosadíme 1, tvrzení opět platí. První krok je splněn.
Předpokládejme, že pro nějaké přirozené číslo \(k\) platí: 6\(\mid\)(\(k\)\(^3\) + 5\(k\)). Dosadíme-li za \(n\) výraz (\(k\) + 1), získáme:
(\(k\) + 1)\(^3\) + 5(\(k\) + 1) = \(k\)\(^3\) + 3\(k\)\(^2\) + 3\(k\) + 1 + 5\(k\) + 5 = \(k\)\(^3\) + 5\(k\) + 3\(k\)\(^2\) + 3\(k\) + 6
Z předpokladu víme, že 6\(\mid\)(\(k\)\(^3\) + 5\(k\)). Zbývá dokázat, že 6\(\mid\)(3\(k\)\(^2\) + 3\(k\) + 6). Ale 3\(k\)\(^2\) + 3\(k\) + 6 = 3(\(k\)\(^2\) + \(k\) + 2) a 6 = 2 · 3. Zbývá tedy dokázat, že 2\(\mid\)(\(k\)\(^2\) + \(k\) + 2), což můžeme provést rozborem, zda je \(k\) liché nebo sudé, totožně jako v přechozím příkladu. Tím bude věta opět dokázána.
☒
