2.4 Ukázka několika důkazů
V této sekci si ukážeme několik jednoduchých důkazů známých a důležitých tvrzení. S dalšími důkazy se čtenář bude moci seznámit v dalších kapitolách tohoto textu. V kapitole 3.6 budeme toto umění dále procvičovat při dokazování několika součtových formulek.
Než se pustíme do našeho prvního důkazu je potřeba si osvěžit několik pojmů, které se v dokazovaném tvrzení budou objevovat. Připomeňme si nejprve pojmy racionálního a iracionálního reálného čísla8.
Definice 2.3
Reálné číslo \(x\), které je podílem dvou celých čísel, nazýváme racionální. Reálné číslo, které není racionální, nazýváme iracionální.
Dále připomeňme pojmy soudělnosti a nesoudělnosti celých čísel.
Definice 2.4
Celá čísla \(m\) a \(n\) nazýváme soudělná, právě když mají společného dělitele většího než \(1\). Pokud celá čísla \(m\) a \(n\) nejsou soudělná, nazýváme je nesoudělná.
Otázka 1
Která z následujících čísel jsou racionální a která iracionální? Proč? \begin{equation*} \frac{\pi}{2}, \ \frac{3}{4}, \ \sin \frac{\pi}{4}, \ \sin \frac{\pi}{6}.\end{equation*}
Otázka 2
Které z následujících dvojic čísel jsou soudělné a které nesoudělné? Proč?
- \(7\) a \(6330079\),
- \(\sqrt{2}\) a \(2\),
- \(5192311\) a \(36551\)
2.4.1 Důkaz sporem
Následující větu dokážeme pomocí tzv. sporu. Myšlenka důkazu sporem je jednoduchá. Jeden z logických axiomů říká, že každé tvrzení \(T\) je buď pravdivé, nebo nepravdivé. Ukážeme-li, že logický opak (negace) tvrzení \(T\) je nepravdivý, pak je původní tvrzení pravdivé.
Věta 2.5
Číslo odmocnina ze \(2\) je iracionální.
Důkaz iracionality \(\sqrt{2}\) :
Předpokládejme opak, tedy že \(\sqrt{2}\) je racionální. Protože se navíc jedná o kladné číslo, existují dle definice racionality dvě přirozená a nesoudělná celá čísla \(p\) a \(q\) splňující \begin{equation*} \sqrt{2} = \frac{p}{q}.\end{equation*} Odtud ale plyne9 rovnost \begin{equation*} 2 = \frac{p^2}{q^2}, \quad \text{čili} \quad 2 q^2 = p^2.\end{equation*} Vidíme, že \(p\) je sudé (jinak bychom měli rovnost sudého a lichého čísla, což je nemožné), tedy10 \(p = 2k\), kde \(k\) je přirozené. Dosazením do rovnice výše a po vydělení obou stran číslem \(2\) dostáváme rovnost \(q^2 = 2k^2\). Použijeme-li stejný argument znovu, dostáváme nutně, že i \(q\) je sudé. Čísla \(p\) i \(q\) jsou soudělná (obě dělitelná číslem \(2\)). Takováto situace ale nemůže nastat. Předpokládali jsme totiž nesoudělnost \(p\) a \(q\), a tím jsme dospěli ke sporu.
\(\square\)Shrňme si tedy ještě jednou princip důkazu sporem. Chceme se přesvědčit o pravdivosti jistého tvrzení \(T\) (tj. chceme ho dokázat). Ukážeme, že logický opak (negace) tvrzení \(T\) neplatí. Tím pádem nutně platí \(T\).
2.4.2 Důkaz matematikou indukcí
Dále si ukážeme důkaz matematickou indukcí. Tento typ důkazu se často používá v případě, že máme nekonečně mnoho tvrzení očíslovaných přirozenými indexy11, tedy například \(T_1, T_2, T_3, \ldots\) Důkaz se provede ve dvou krocích:
- dokaž první tvrzení, zde \(T_1\),
- pro libovolné přirozené \(n\) dokaž tzv. indukční krok: pokud platí \(T_n\), pak platí \(T_{n+1}\).
Obrázek 2.1: Schéma důkazu matematickou indukcí. Místo abychom dokázali všechna \(T_n\), \(n=1,2,\ldots\), dokážeme \(T_1\) a indukční krok, tj. tvrzení \(T_n \Rightarrow T_{n+1}\) (červené šipky).
Matematickou indukci lze přirovnat k bourání hada sestaveného z dominových kostek. Každá kostka domina představuje „výrok“ a může se nacházet ve dvou stavech. Kostka může být stojící, nebo spadlá (podobně výrok může být pravdivý, nebo nepravdivý). Pokud chceme zjistit, jestli námi sestavený dominový had celý spadl, máme dvě možnosti. Můžeme zkontrolovat každou z kostek a zjistit, jestli spadla12. Druhou možností je zkontrolovat tyto skutečnosti:
- první kostka spadla,
- dvě sousední kostky jsou umístěny v takové vzdálenosti, že pokud spadne první (ta blíže první kostce), pak spadne i její soused (analog indukčního kroku).
Ukažme si důkaz pomocí matematické indukce na tzv. binomické větě. V tvrzení věty používáme zkrácený zápis součtu, tzv. sumační notaci, o které se čtenář může podrobněji dozvědět v sekci 3.6. O kombinačních číslech se zmíníme v sekci 3.7.
Věta 2.6 (Binomická)
Pro reálná čísla \(a\) a \(b\) a celé nezáporné číslo \(n\), tj. pro \(a,b\in\mathbb{R}\) a \(n\in \mathbb{N}_0\), platí rovnost
Důkaz binomické věty matematickou indukcí :
Ověřme, že zkoumaná rovnost platí pro první uvažované \(n\), tj. pro \(n=0\). Levá strana (2.1) je rovna \((a+b)^0 = 1\) a pro pravou stranu téže rovnosti platí \begin{equation*} \sum_{k=0}^0 \binom{0}{k} a^k b^{0-k} = 1 \cdot 1 \cdot 1 = 1.\end{equation*} Rovnost \(1=1\) je jistě pravdivá. Předpokládejme nyní, že (2.1) platí pro dané \(n \in \mathbb{N}_0\). Ověřme, zda-li platí (2.1) pro \(n+1\) místo \(n\). Chceme tedy zjistit, zda-li \begin{equation*} (a+b)^{n+1} = \sum_{k=0}^{n+1} \binom{n+1}{k} a^k b^{n+1-k}.\end{equation*} Přímočarým výpočtem dostáváme13 \begin{align*} (a+b)^{n+1} & \href{Obecně pro reálné \(z\) platí \(z^{n+1} = z \cdot z^n\).}{\class{mathpopup}{=}} (a+b)\cdot(a+b)^n \href{Indukční předpoklad: binomická věta platí pro zvolené \(n\).}{\class{mathpopup}{\overset{!}{=}}} (a+b) \sum_{k=0}^n \binom{n}{k} a^k b^{n-k} = \\ & \href{Roznásobení závorky a vynásobení sum čísly \(a\) a \(b\).}{\class{mathpopup}{=}} \sum_{k=0}^n \binom{n}{k} a^{k+1} b^{n-k} + \sum_{k=0}^n \binom{n}{k} a^k b^{n+1-k} = \\ & \href{Posunutí indexu v první sumě, přeindexováním získáme sčítance stejného tvaru jako v druhé sumě.}{\class{mathpopup}{=}} \sum_{k=1}^{n+1} \binom{n}{k-1} a^k b^{n+1-k} + \sum_{k=0}^n \binom{n}{k} a^k b^{n+1-k} = \\ & \href{Sčítání přes společný rozsah indexů. Dva členy z každé sumy zůstanou osamoceny.}{\class{mathpopup}{=}} \underbrace{\binom{n}{n} a^{n+1} b^{n+1-(n+1)}}_{a^{n+1}} + \sum_{k=1}^n \Bigg( \underbrace{\binom{n}{k-1} + \binom{n}{k}}_{\binom{n+1}{k}} \Bigg) a^k b^{n+1 -k} + \\ &+ \underbrace{\binom{n}{0} a^0 b^{n+1-0}}_{b^{n+1}} = \\ & \href{Zjednodušení výrazu znázorněné v předchozím výrazu a vyjádření všech členů pomocí jedné sumy.}{\class{mathpopup}{=}} \sum_{k=0}^{n+1} \binom{n+1}{k} a^k b^{n+1-k}.\end{align*} V rovnosti označené vykřičníkem jsme použili indukční předpoklad (platnost vztahu pro \(n\)) a dále jsme jen prováděli algebraické operace. Pokud přečteme začátek a konec tohoto výpočtu uvidíme, že jsme odvodili vztah pro \(n+1\), což bylo naším cílem.
\(\square\)Tvrzení binomické věty obsahuje dobře známé algebraické „vzorečky“ \begin{equation*} \begin{aligned} (a+b)^2 &= a^2 + 2ab + b^2, \\ (a+b)^3 &= a^3 + 3a^2b + 3ab^2 + b^3. \end{aligned}\end{equation*} Tyto vzorce představují speciální případy binomické věty pro konkrétní volbu \(n\). Pro tato malá konkrétní \(n\) je možné tyto vzorce snadno alternativně ověřit pomocí roznásobení závorek. Například pro první rovnost, tedy pro \(n=2\) máme \begin{equation*} (a+b)^2 \href{Definice druhé mocniny.}{\class{mathpopup}{=}} (a+b)\cdot (a+b) \href{Distributivní zákon, resp. roznásobení dvou závorek.}{\class{mathpopup}{=}} a^2 + ab + ba + b^2 \href{Komutativita násobení.}{\class{mathpopup}{=}} a^2 + 2ab + b^2.\end{equation*} Tento výpočet efektivně dokazuje binomickou větu pro \(n=2\). I když podobným způsobem ověříme platnost této věty pro \(n=3\) nelze to považovat za důkaz binomické věty. Chyběl by nám důkaz pro \(n=3,4,5,\ldots\)! Naštěstí jsme tato tvrzení dokazovat nemuseli, stačilo použít matematickou indukci.
Význam binomické věty lze dále demonstrovat na konkrétním příkladě (někdo by řekl „triku“). Představme si, že máme rychle z hlavy spočítat \(48^2\). Můžeme využít toho, že číslo \(48\) je blízko čísla \(50\), jehož druhá mocnina se snadno počítá. Konkrétně dle binomické věty máme \begin{equation*} 48^2 = (50 - 2)^2 \href{V binomické větě zvolme \(a=50\), \(b=-2\), \(n = 2\).}{\class{mathpopup}{=}} 50^2 - 2 \cdot 50 \cdot 2 + 4 = 2500 - 200 + 4 = 2304.\end{equation*}
Otázka 3
Čemu se rovná součet prvních \(n\) lichých přirozených čísel? Tj. čemu se rovná součet \begin{equation*} 1 + 3 + 5 + \cdots + (2n-1) = \sum_{j=1}^n (2j-1), \quad n \in \mathbb{N}.\end{equation*} Své tvrzení dokažte.
2.4.3 Přímý důkaz
Dalším typem důkazu je tzv. přímý důkaz. Takříkajíc bez oklik, přímočaře, z předpokladů odvodíme tvrzení. Uvažme následující větu.
Věta 2.7
Pro libovolná reálná \(a\) a \(b\) a \(n \in \mathbb{N}_0\) platí rovnost
Mějme tedy \(a,b \in \mathbb{R}\) a \(n \in \mathbb{N}_0\). Máme dokázat rovnost (2.2). Vyjděme z pravé strany této rovnosti a postupnými algebraickými úpravami ji upravme až získáme levou stranu (2.2). Konkrétně \begin{equation*} \begin{aligned} (a-b) \sum_{k=0}^{n-1} a^k b^{n-1-k} & \href{Roznásobení závorky.}{\class{mathpopup}{=}} a \cdot \sum_{k=0}^{n-1} a^k b^{n-1-k} - b\cdot \sum_{k=0}^{n-1} a^k b^{n-1-k} = \\ & \href{Roznásobení sum čísly \(a\) a \(b\).}{\class{mathpopup}{=}} \sum_{k=0}^{n-1} a^{k+1} b^{n-1-k} - \sum_{k=0}^{n-1} a^k b^{n-k} = \\ & \href{Posunutí sčítacího indexu v první sumě.}{\class{mathpopup}{=}} \sum_{k=1}^{n} a^{k} b^{n-k} - \sum_{k=0}^{n-1} a^k b^{n-k} = \\ & \href{Vyjmutí posledního členu z první sumy a prvního členu z druhé sumy.}{\class{mathpopup}{=}} a^n + \sum_{k=1}^{n-1} a^{k} b^{n-k} - b^n - \sum_{k=1}^{n-1} a^k b^{n-k} = \\ & \href{Odečtení stejných sum.}{\class{mathpopup}{=}} a^n - b^n. \end{aligned}\end{equation*} Jinak řečeno, po roznásobení sumy závorkou \((a-b)\) se drtivá většina členů vzájemně odečte a zbude pouze rozdíl \(a^n - b^n\).
\(\square\)Alternativně by bylo možné větu 2.7 dokázat i pomocí matematické indukce (proveďte!). Pod tvrzení věty 2.7 se skrývají známé speciální případy: \begin{equation*} \begin{aligned} a^2 - b^2 &= (a-b)(a+b), \\ a^3 - b^3 &= (a-b)(a^2 + ab + b^2). \end{aligned}\end{equation*} Tyto vzorce a obecný vzorec 2.2 se nám budou v budoucnu hodit (nejen) při výpočtu limit. V čem je věta 2.7 tak užitečná? Umožňuje nám vyjádřit rozdíl stejných mocnin dvou čísel pomocí rozdílu čísel samotných. Jinak řečeno, pokud máme nějakou informaci o rozdílu \(a-b\), pak pomocí této věty lze něco usoudit i o rozdílu \(a^n - b^n\).
Poznámka 2.8
V dokázaném vzorci (2.2) je obsažen i vzorec pro součet prvních několika členů geometrické posloupnosti s prvním členem \(1\) a kvocientem \(q\). Skutečně, uvážíme-li v tomto vzorci \(a = q \neq 1\) a \(b = 1\), pak dostanem \begin{equation*} q^n - 1 = (q - 1) \sum_{k=0}^{n-1} q^k\end{equation*} a po vydělení nenulovým faktorem \(q - 1\) \begin{equation*} \sum_{k=0}^{n-1} q^k = \frac{q^n - 1}{q - 1}.\end{equation*}
Poznámka 2.9
Další užitečnou aplikací (2.2) je možnost „zbavit se odmocnin“. Přesněji, představme si, že pracujeme s výrazem tvaru \(\sqrt{x} - \sqrt{y}\) a chtěli bychom využít naší znalosti samotného rozdílu \(x - y\). Jak toho docílit? Stačí vzorec (2.2) použít ve tvaru \begin{equation*} a - b = \frac{a^2 - b^2}{a + b}\end{equation*} a položit \(a = \sqrt{x}\), \(b = \sqrt{y}\). Tím dostaneme \begin{equation*} \sqrt{x} - \sqrt{y} = \frac{x - y}{\sqrt{x} + \sqrt{y}},\end{equation*} přesně jak jsme chtěli. Nově vzniknuvší jmenovatel nás většinou netrápí, protože se v něm provádí součet, ne rozdíl. Podobnou úpravu lze udělat i pro vyšší odmocniny i různého řádu. Dále je tato úprava důležitá i z pohledu numerických výpočtů na počítači. Lze se pomocí ní alespoň trochu bránit tzv. katastrofickému krácení při odečítání podobně velkých hodnot ve strojové přesnosti.