2.4 Ukázka několika častých typů důkazů

1 Úvod 2 Matematika není jen počítání 2.1 Počítání a abstrakce 2.2 Struktura matematického textu 2.3 Co je to důkaz? 2.4 Ukázka několika častých typů důkazů 2.5 Co není důkaz? 3 Základní pojmy 4 Elementární funkce 5 Analytická geometrie 6 Časté problémy 7 Přehled použitého značení Index Literatura

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 čísla¹¹.

Definice 2.1

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.2

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á.

Pro úplnost ještě dodejme definici dělitelnosti celých čísel využitou v předchozí definici.

Definice 2.3

Celé číslo $m$ dělí celé číslo $n$ (symbolicky píšeme $m | n$), právě když existuje celé číslo $k$ takové, že $n = k \cdot m$.

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 tedy, že logický opak (negace) tvrzení $T$ je nepravdivý, pak je původní tvrzení $T$ pravdivé. Ona nepravdivost se projeví právě oním sporem. Pojďme rovnou k názorné ukázce.

Věta 2.1

Číslo odmocnina ze $2$, které označujeme symbolem $\sqrt{2}$, je iracionální.

Poznámka 2.2

Poznamenejme, že $\sqrt{2}$ je takové jediné kladné reálné číslo, které splňuje vztah $\big( \sqrt{2} \big)^2 = 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 plyne¹² 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é¹³), tedy¹⁴ $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 proto 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.

Čísla $p$ a $q$ nemohou být současně soudělná i nesoudělná. Tato očividná nepravdivost představuje spor.

$\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$.

Otázka 2.1

Která z následujících čísel jsou racionální a která iracionální? Proč?

\begin{equation*} \frac{\pi}{2}, \quad \frac{3}{4}, \quad \sin \frac{\pi}{4}, \quad \sin \frac{\pi}{6}. \end{equation*}

Zobrazit odpověď

Racionální jsou $\frac{3}{4}$ a $\sin \frac{\pi}{6} = \frac{1}{2}$, protože je lze napsat jako podíl celých čísel, přesně dle definice. Iracionální jsou $\frac{\pi}{2}$ a $\sin\frac{\pi}{4} = \frac{\sqrt{2}}{2}$ protože víme, že $\pi$ a $\sqrt{2}$ jsou iracionální čísla.

Otázka 2.2

Které z následujících dvojic čísel jsou soudělné a které nesoudělné? Proč?

$7$ a $6\,330\,079$,
$\sqrt{2}$ a $2$,
$5\,192\,311$ a $36\,551$.

Zobrazit odpověď

1. soudělná (obě dělí $7$), 2. ani nesoudělná, ani soudělná, nejedná se o dvojici celých čísel, 3. nesoudělná (obě jsou prvočísla).

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 indexy¹⁵, 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}$.

Grafické znázornění tohoto postupu je na obrázku 2.1. Indukčnímu kroku odpovídají červené šipky. První bod, důkaz $T_1$, je naznačen modrou barvou.

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 spadla¹⁶. 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 (tento bod představuje analog indukčního kroku).

Potom automaticky víme, že spadly všechny kostky. Zdůrazněme podstatný rozdíl v těchto argumentačních přístupech. Druhý způsob (tj. matematická indukce) kontroluje stav pouze první kostky, u ostatních se nedívá jestli stojí nebo ne, pouze jsou-li u sebe dostatečně blízko.

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.2 (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

\begin{equation}\label{eqBinomicka}\tag{2.1} (a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}. \end{equation}

Poznámka 2.3

Nejjednoduší interpretace vzorce (2.1) spočívá v explicitním roznásobení závorky na levé straně a určení koeficientů členů ve výsledném součtu (kombinační čísla). Díky binomické větě tak nemusíme výrazy typu $(a+b)^n$ sami ručně otrocky roznásobovat (pokud je z nějakého důvodu chceme v roznásobeném tvaru).

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 rovnost (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 za uvedeného předpokladu platí i rovnost

\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áme¹⁷

\begin{align*} (a+b)^{n+1} & \href{Obecně pro reálné $z$ platí $z^{n+1} = z \cdot z^n$.}{\class{mathpopup bg-info-subtle}{=}} (a+b)\cdot(a+b)^n \href{Indukční předpoklad: binomická věta platí pro zvolené $n$.}{\class{mathpopup bg-info-subtle}{\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 bg-info-subtle}{=}} \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 bg-info-subtle}{=}} \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 bg-info-subtle}{=}} \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 bg-info-subtle}{=}} \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{align*} (a+b)^2 &= a^2 + 2ab + b^2, \\ (a+b)^3 &= a^3 + 3a^2b + 3ab^2 + b^3.\end{align*}

Tyto vzorce představují speciální případy binomické věty pro konkrétní volbu $n$ (zde $n = 2$ a $n = 3$). Pro tato malá konkrétní $n$ je možné tyto vzorce snadno alternativně ověřit pomocí roznásobení závorek, ale v tento okamžik je to zbytečné, přidělávali bychom si práci. Například pro první rovnost, tedy pro $n=2$ máme

\begin{equation*} (a+b)^2 \href{Definice druhé mocniny.}{\class{mathpopup bg-info-subtle}{=}} (a+b)\cdot (a+b) \href{Distributivní zákon, resp. roznásobení dvou závorek.}{\class{mathpopup bg-info-subtle}{=}} a^2 + ab + ba + b^2 \href{Komutativita násobení.}{\class{mathpopup bg-info-subtle}{=}} 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=4,5,6,\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 bg-info-subtle}{=}} 50^2 - 2 \cdot 50 \cdot 2 + 4 = 2500 - 200 + 4 = 2304. \end{equation*}

Otázka 2.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.

Zobrazit odpověď

$\sum_{j=1}^n (2j - 1) = n^2$. Tento vztah laskavý čtenář snadno dokáže pomocí matematické indukce.

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.3

Pro libovolná reálná $a$ a $b$ a $n \in \mathbb{N}_0$ platí rovnost

\begin{equation}\label{eqAnBn}\tag{2.2} a^n - b^n = (a-b) \sum_{k=0}^{n-1} a^k b^{n-1-k}. \end{equation}

Zobrazit důkaz

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 bg-info-subtle}{=}} 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 bg-info-subtle}{=}} \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 bg-info-subtle}{=}} \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 bg-info-subtle}{=}} 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 bg-info-subtle}{=}} 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.3 dokázat i pomocí matematické indukce (proveďte!). Pod tvrzením věty 2.3 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.3 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$.

Další aplikací této věty je snadné odvození vzorce pro součet prvních několika členů geometrické posloupnosti.

Poznámka 2.4

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 dostaneme

\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.5

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.