Přednáška 2

Logika a důkazy. Matematická indukce

Výroky a logické spojky, výrokové formy, výrokové formule, pravdivostní tabulky, kvantifikátory, definice a věty, přímý a nepřímý důkaz, důkaz sporem, matematická indukce, rekurentní posloupnosti, kombinační čísla a binomická věta.

PDF

Logika a důkazy

Dalším běžným prostředkem „matematičtiny“ je symbolika výrokové a predikátové logiky. Matematika totiž zkoumá umělé světy, které mimo jiné mimořádně dobře slouží k modelování reality. Jak jsme se již zmínili v předchozí přednášce, matematická tvrzení mají jednu zásadní vlastnost: vždy má smysl ptát se, zda platí, nebo neplatí. To zajišťuje jednoznačnost a spolehlivost výsledků. Existují sice i otevřené matematické problémy, ty jsou však otevřené hlavně proto, že jejich důkaz – ať už pravdivosti, či nepravdivosti – zatím nikdo nenašel.

Matematická tvrzení je výhodné zapisovat ve zkrácené formě pomocí symbolů, které mají původ v matematické logice. Díky tomuto přístupu se snáz odhaluje logická struktura tvrzení, která by jinak mohla zůstat skryta za spletitými slovními obraty přirozeného (tedy například českého) jazyka. Každý přirozený jazyk totiž ponechává prostor pro různé obsahové interpretace. Výroková logika pomáhá uspořádat a vyjádřit myšlenky způsobem blízkým běžnému lidskému vyjadřování a přitom zajistit jejich přesnost i jednoznačnost.

Definice 2.1Výrok#

Výrok je tvrzení, u nějž má smysl otázka, zda je pravdivé (platí), nebo není pravdivé (neplatí). Pokud výrok platí, říkáme, že má pravdivostní hodnotu $1$ ; pokud neplatí, má pravdivostní hodnotu $0$ .

Výroky zpravidla značíme velkými latinskými písmeny, případně s dolními indexy – například $A$ , $B$ nebo $C_1$ .

Poznámka 2.2Výroková forma#

Velmi často se setkáme s výroky závislými na parametru (dokonce i mnoha parametrech), tzv. výrokovými formami nebo predikáty. Pokud tvrzení $A$ závisí na parametru $x$ , zapisujeme jej jako $A(x)$ . Pro různá $x$ tak dostáváme různé výroky, které mohou být buď pravdivé, nebo nepravdivé.

Podrobně se výrokovým formám v rámci tohoto přípravného kurzu věnovat nebudeme – setkáte se s nimi v matematických předmětech prvního ročníku. Něco málo však ještě budeme potřebovat v druhé části této přednášky.

Příklad 2.3#

Pouze některé gramaticky správné věty jsou výroky:

„Na Jaderce lze studovat matematiku.“ je pravdivý výrok.
„Jaderka je lehká škola – lze tady udělat zkoušky levou zadní.“ je nepravdivý výrok.
„Číslo 2 je sudé.“ je výrok s pravdivostní hodnotou $1$ .
„Brno je hlavní město České republiky.“ je výrok s pravdivostní hodnotou $0$ .
„ $5 < 4$ .“ je výrok, který neplatí.
„ $\sqrt{2}$ je iracionální.“ je platný výrok.
„Mimozemšťané existují.“ je výrok, i když zatím není známo, zda je pravdivý, či nepravdivý.
„Ahoj!“ není výrok – nedává smysl se bavit o jeho pravdivosti.
„Kéž by už byl konec přednášky.“ výrok není.

Z jednotlivých výroků si můžeme vytvářet nové složitější výroky (tzv. výrokové formule) pomocí logických operací. Se základními logickými operacemi se nyní seznámíme.

Definice 2.4Negace#

Negací výroku $A$ rozumíme výrok „Není pravda, že platí $A$ .“, značíme ji $\neg A$ .

Je-li výrok $A$ pravdivý, pak je výrok $\neg A$ nepravdivý. Naopak, je-li výrok $A$ nepravdivý, bude výrok $\neg A$ pravdivý.

Přímo z definice negace můžeme sestrojit odpovídající pravdivostní tabulku 1. Pravdivostní tabulky jsou totiž základním nástrojem, který pomáhá zkoumat „chování“ výrokových formulí.

$A$	$\neg A$
$0$	$1$
$1$	$0$

Tabulka 1: Pravdivostní tabulka ilustrující operaci negace.

Příklad 2.5#

Negaci lze často vyslovit kratším a srozumitelnějším způsobem: použijeme obrat „Neplatí $A$ .“, nebo „otočíme“ sloveso přidáním předpony „ne-“. Nejčastěji se ale budeme snažit vyslovit negaci co nejpřirozeněji a nejjednodušeji:

Negaci výroku „Na Jaderce lze studovat matematiku.“ můžeme vyslovit jako „*Na Jaderce nelze studovat matematiku.*“ Vyjde nám nepravdivý výrok – původní totiž pravdivý je; právě tuto úctyhodnou akci teď společně uskutečňujeme.
Negací výroku „Daný trojúhelník $ABC$ je ostroúhlý.“ bude výrok „Daný trojúhelník $ABC$ je pravoúhlý nebo tupoúhlý.“
Znegováním neplatného výroku „ $5 < 4$ .“ dostaneme platný výrok „ $5 \geq 4$ .“.
Negací výroku „ $\sqrt{2}$ je iracionální.“ s pravdivostní hodnotou $1$ je výrok „ $\sqrt{2}$ je racionální.“, který má pravdivostní hodnotu $0$ .
Výrok „Prvočísel je nekonečně mnoho.“ je pravdivý, jeho negace „Prvočísel je konečně mnoho.“ pravdivá není.
Bude negací výroku „Číslo 2 je sudé.“ výrok „Číslo 2 je liché.“? Ano – ale jen díky tomu, že v univerzu celých čísel víme, že každé z nich je buď sudé, nebo liché. Samotná logika nám to neřekne: doslovná negace zní „Číslo 2 není sudé.“ Kdybychom totéž zkusili s necelým reálným číslem, narazili bychom na problém: pojmy sudosti a lichosti pro takové číslo vůbec nejsou definovány, a o korektně vyslovené výroky by tedy nešlo.

Definice 2.6Konjunkce#

Konjunkcí výroků $A$ a $B$ je výrok „Platí $A$ a zároveň platí $B$ .“ Alternativně můžeme použít například stručnější slovní obraty „Platí $A$ a platí $B$ .“, „Platí $A$ i $B$ .“ Konjunkci výroků $A$ a $B$ značíme $A \land B$ .

Pokud jsou pravdivé oba výroky $A$ a $B$ , pak je konjunkce $A \land B$ pravdivá; pokud je alespoň jeden z výroků $A$ a $B$ nepravdivý, pak je konjunkce $A \land B$ nepravdivá.

Definice 2.7Disjunkce#

Disjunkcí výroků $A$ a $B$ rozumíme výrok „Platí $A$ nebo $B$ .“, značíme ji $A \lor B$ . Pokud je alespoň jeden z výroků $A$ a $B$ pravdivý, pak je disjunkce $A \lor B$ pravdivá; pokud jsou oba výroky $A$ a $B$ nepravdivé, pak je disjunkce $A \lor B$ nepravdivá.

Poznámka 2.8#

Poznamenejme, že v matematice spojka „nebo“, tedy disjunkce, nemá vylučovací význam. To znamená, že je pravdivá i v případě, kdy platí oba výroky $A$ a $B$ zároveň. V přirozeném jazyce může spojka „nebo“ mít i vylučovací význam – na to máme v matematice jinou operaci, která však nepatří mezi ty základní.

Teď se blížíme k těm nejzajímavějším logickým operacím, které budeme běžně potřebovat k vyjadřování matematických myšlenek – a které používáme i v běžné řeči, aniž bychom si to uvědomovali. Dokonce i v tomto textu jsme je již mnohokrát použili.

Definice 2.9Implikace#

Implikací výroků $A$ a $B$ nazýváme výrok „Pokud platí $A$ , pak platí $B$ .“ Tento nový výrok značíme $A \implies B$ .

Implikace je pravdivá, platí-li oba výroky $A$ i $B$ , a rovněž tehdy, neplatí-li výrok $A$ . V jediném zbylém případě, kdy $A$ platí a zároveň $B$ neplatí, jde o implikaci nepravdivou.

Výroku $A$ se říká předpoklad a výroku $B$ závěr implikace. O výroku $A$ také říkáme, že je postačující podmínkou pro platnost výroku $B$ ; naopak výrok $B$ je nutnou podmínkou platnosti výroku $A$ .

Poznámka 2.10#

Pro vyjádření implikace slovy také používáme následující obraty:

„Jestliže platí výrok $A$ , pak platí výrok $B$ .“
„Výrok $A$ implikuje výrok $B$ .“
„Z výroku $A$ plyne výrok $B$ .“
„Předpokládejme, že platí výrok $A$ , potom platí výrok $B$ .“
„Nechť platí výrok $A$ . Potom platí výrok $B$ .“
„Výrok $B$ je důsledkem výroku $A$ .“

Poznámka 2.11#

Zdůrazníme si, že je-li předpoklad $A$ nepravdivý, pak implikace $A \implies B$ platí vždy bez ohledu na platnost závěru $B$ . Jinými slovy, z nepravdivého výroku plyne jakýkoliv jiný výrok. Tato skutečnost může zpočátku působit potíže, které vyplývají z poněkud rozdílného používání obratu „Jestliže platí $A$ , pak platí $B$ .“ v logice a v přirozeném jazyce. V běžné řeči používáme tento obrat zpravidla tehdy, existuje-li nějaká věcná souvislost mezi $A$ a $B$ , zatímco v logice používáme tento obrat i ke spojení výroků, kde taková souvislost ani nemusí existovat, například „Jestliže medvědi umí létat, pak jsou Athény v Egyptě.“ Pravdivost takového výroku v logice závisí pouze na pravdivostních hodnotách předpokladu a závěru. Ačkoliv pravdivost takových výroků může na první pohled působit překvapivě, je toto ryze logické pojetí implikace v matematice velmi užitečné.

Jiným příkladem implikace může být „Pokud získám u zkoušky z analýzy A, dostanu od rodičů čokoládový bonbon.“ Pokud předpoklad platit nebude, tj. pokud z analýzy áčko nezískáme, nelze o druhé části nic usoudit – bonbon můžeme i přesto dostat (například za úspěšnou zkoušku z lineární algebry) anebo nedostat. Implikace jako celek přitom zůstává pravdivá v obou případech.

Definice 2.12Ekvivalence#

Ekvivalence výroků $A$ a $B$ je výrok „Výrok $A$ platí právě tehdy, když platí výrok $B$ .“ Značíme ji $A \iff B$ . Pokud $A$ a $B$ mají stejnou pravdivostní hodnotu, pak je ekvivalence $A \iff B$ pravdivá; pokud nemají $A$ a $B$ stejnou pravdivostní hodnotu, pak je $A \iff B$ nepravdivý výrok.

O výroku $A$ v tomto případě říkáme, že je nutnou a postačující podmínkou platnosti výroku $B$ (a naopak, jelikož ekvivalence je zřejmě symetrickou operací).

Poznámka 2.13#

Ekvivalence se také může vyjadřovat například pomocí následujících slovních obratů:

„Výrok $A$ platí tehdy a jen tehdy, když platí výrok $B$ .“
„Výrok $A$ je ekvivalentní výroku $B$ .“
„Výroky $A$ a $B$ platí zároveň, anebo zároveň neplatí.“

Shrneme výše uvedené definice binárních logických operací do pravdivostní tabulky 2.

$A$	$B$	$A \land B$	$A \lor B$	$A \implies B$	$A \iff B$
$0$	$0$	$0$	$0$	$1$	$1$
$0$	$1$	$0$	$1$	$1$	$0$
$1$	$0$	$0$	$1$	$0$	$0$
$1$	$1$	$1$	$1$	$1$	$1$

Tabulka 2: Pravdivostní tabulka základních binárních logických operací.

Definice 2.14Obrácená implikace#

Obrácenou implikací k implikaci $A \implies B$ nazýváme výrok $B \implies A$ .

Definice 2.15Obměněná implikace#

Obměněnou implikací k implikaci $A \implies B$ nazýváme výrok $\neg B \implies \neg A$ .

Poznámka 2.16#

Všimněme si, že obrácená implikace spočívá v prohození předpokladu a závěru. S původní implikací proto ekvivalentní není. Obměněná implikace s ní naopak ekvivalentní zaručeně je – viz tabulku 3. Jejich ekvivalence s výhodou využijeme dále.

$A$	$B$	$\neg A$	$\neg B$	$A \implies B$	$B \implies A$	$\neg B \implies \neg A$
$0$	$0$	$1$	$1$	$1$	$1$	$1$
$0$	$1$	$1$	$0$	$1$	$0$	$1$
$1$	$0$	$0$	$1$	$0$	$1$	$0$
$1$	$1$	$0$	$0$	$1$	$1$	$1$

Tabulka 3: Obrácená a obměněná implikace.

Zbývá doplnit dva symboly, bez nichž se při zápisu převážné většiny matematických tvrzení neobejdeme. Vracejí nás k výrokovým formám z poznámky 2.2: dosud jsme uměli mluvit o konkrétních výrocích, teď se naučíme jedním stručným zápisem obsáhnout celou jejich množinu.

Označení 2.17Obecný a existenční kvantifikátor#

Nechť $A(x)$ je výroková forma s parametrem $x$ probíhajícím jistou množinu $M$ . Zavádíme dva kvantifikátory:

$(\forall x \in M)\, A(x)$ – obecný (všeobecný, univerzální) kvantifikátor. Čteme „Pro každé $x$ z množiny $M$ platí $A(x)$ “. Tento výrok je pravdivý právě tehdy, když je $A(x)$ pravdivý výrok pro všechny prvky $x$ množiny $M$ .
$(\exists x \in M)\, A(x)$ – existenční kvantifikátor. Čteme „Existuje $x$ z množiny $M$ takové, že platí $A(x)$ “. Tento výrok je pravdivý právě tehdy, když je $A(x)$ pravdivý výrok alespoň pro jeden prvek $x$ množiny $M$ .

Poznámka 2.18#

Ke kvantifikátorům patří tři poznámky, na kterých se dá snadno uklouznout.

Existenční kvantifikátor znamená „alespoň jeden“, nikoli „právě jeden“. Chceme-li tvrdit, že takový prvek existuje a je jediný, používáme tzv. kvantifikátor existence a jednoznačnosti, označovaný $\exists!$ nebo $\exists_1$ . Ten však mezi základní symboly matematické logiky nepatří; je přesto u matematiků velmi oblíbený.
Na pořadí kvantifikátorů záleží. Výroky

$(\forall x \in \R)(\exists y \in \R)\,(y > x) \qquad \text{a} \qquad (\exists y \in \R)(\forall x \in \R)\,(y > x)$

se liší jen prohozením dvou závorek, přesto je první pravdivý (ke každému reálnému číslu najdeme větší) a druhý nepravdivý (žádné reálné číslo není větší než všechna ostatní).
Negace kvantifikovaného výroku oba kvantifikátory prohazuje:

$\begin{gathered} \neg\bigl((\forall x \in M)\, A(x)\bigr) \iff (\exists x \in M)\, \neg A(x),\\ \neg\bigl((\exists x \in M)\, A(x)\bigr) \iff (\forall x \in M)\, \neg A(x). \end{gathered}$

Tedy aby neplatilo tvrzení o všech, stačí jediná výjimka; a aby neplatilo tvrzení o existenci, nesmí vyhovovat nikdo. Negací výroku „Všichni studenti Jaderky mají rádi matematiku.“ je tedy „Alespoň jeden student Jaderky nemá rád matematiku.“ (pak ovšem není jasné, jak přežije studium v prvním ročníku; čistě teoreticky se to ale stát může), nikoliv „Žádný student Jaderky nemá rád matematiku.“ (to by bylo neuvěřitelné neštěstí).

Zavedené symboly nám umožňují popsat logickou stavbu matematických textů. Podívejme se aspoň krátce na dva jejich nejčastější stavební kameny – definice a věty. Podrobněji se prací s logickými operacemi a kvantifikátory budete zabývat v dalších matematických předmětech prvního ročníku.

Poznámka 2.19Definice a věty#

Definice zavádí nový pojem. Musí přitom pro každý objekt z uvažovaného oboru jednoznačně rozhodnout, zda pod nový pojem spadá, či nikoliv. Ačkoliv se definice tradičně píší ve tvaru „objekt nazýváme …, pokud platí …“, ve skutečnosti jde vždy o ekvivalenci; občas se proto v definicích setkáte i se zápisem $\overset{\text{def}}{\iff}$ .

Věty (a také tvrzení, lemmata či důsledky) mívají tvar implikace „platí-li předpoklady, platí i závěr“, případně ekvivalence. U každé věty se proto vyplatí hned si ujasnit, co je předpoklad a co závěr. Typickou chybou je totiž zaměnit větu za implikaci obrácenou – a ta, jak už víme, platit nemusí.

Zbývá otázka, jak takové implikace dokazovat. Základní tři postupy vycházejí přímo z pravdivostních tabulek sestavených výše.

Poznámka 2.20Přímý a nepřímý důkaz, důkaz sporem#

Chceme dokázat implikaci $A \implies B$ , tedy typickou situaci matematické věty, kdy z platného předpokladu $A$ potřebujeme odvodit závěr $B$ .

Přímý důkaz. Z předpokladu $A$ odvodíme řetěz platných implikací vedoucí k $B$ :

$A \implies A_1 \implies A_2 \implies \ldots \implies B.$
Nepřímý důkaz. Místo $A \implies B$ dokážeme implikaci obměněnou, tedy $\neg B \implies \neg A$ . Že to stačí, jsme ověřili v tabulce 3 – obě implikace mají v každém řádku tutéž pravdivostní hodnotu.
Důkaz sporem. Předpokládáme, že $A$ platí a zároveň $B$ neplatí, a z toho odvodíme zjevně nepravdivý výrok. Kombinace $A \wedge \neg B$ je totiž jediná, při níž je implikace $A \implies B$ nepravdivá (viz tabulku 2); pokud vede ke sporu, nemůže nastat, a implikace tedy platí. Důkaz sporem je právem jednou z nejúčinnějších a nejpoužívanějších důkazových metod v matematice.

Poznámka 2.21#

Nepřímý důkaz a důkaz sporem se snadno pletou. Rozdíl je v tom, kam směřují: u nepřímého důkazu odvozujeme konkrétní závěr $\neg A$ , tedy negaci předpokladu, zatímco u důkazu sporem stačí dojít k jakémukoliv nesmyslu. Nepřímý důkaz je tak vlastně zvláštním případem důkazu sporem.

Všechny tři postupy si nyní vyzkoušíme – a to tak, aby na sebe navazovaly: každý dokázaný výsledek použijeme v tom následujícím.

Přímý důkaz

Nejznámější větu tohoto typu znáte ze základní školy, i když se obvykle neformuluje jako implikace.

Věta 2.22Pythagorova#

Nechť $ABC$ je trojúhelník s délkami stran $a$ , $b$ , $c$ . Je-li trojúhelník $ABC$ pravoúhlý s přeponou $c$ , pak

$a^2 + b^2 = c^2.$

Důkaz

Ze čtyř kopií daného pravoúhlého trojúhelníku sestavíme čtverec o straně $a+b$ tak, jak ukazuje obrázek 3. Vnitřní čtyřúhelník má všechny strany délky $c$ . Jeho vnitřní úhly jsou navíc pravé: v každém jeho vrcholu se na přímce potkávají oba ostré úhly pravoúhlého trojúhelníku a jeden úhel čtyřúhelníku, a protože oba ostré úhly dávají dohromady $90^\circ$ , zbývá na úhel čtyřúhelníku právě $90^\circ$ . Jde tedy o čtverec o straně $c$ .

Obrázek 3: Čtyři kopie pravoúhlého trojúhelníku s odvěsnami $a$ , $b$ a přeponou $c$ vyplňují čtverec o straně $a+b$ tak, že uprostřed zbude čtverec o straně $c$ .

Obsah velkého čtverce spočítáme dvěma způsoby: jednak přímo, jednak jako součet obsahu vnitřního čtverce a čtyř trojúhelníků. Dostáváme

$\left(a+b\right)^2 = c^2 + 4 \cdot \frac{ab}{2}.$

Roznásobením levé strany máme $a^2 + 2ab + b^2 = c^2 + 2ab$ a po odečtení $2ab$ zbývá $a^2 + b^2 = c^2$ .

Poznámka 2.23#

Všimněme si, že věta 2.22 je implikace: předpokladem je pravoúhlost trojúhelníku, závěrem vztah mezi délkami jeho stran. Platí i implikace obrácená (je-li $a^2+b^2 = c^2$ , je trojúhelník pravoúhlý), jde však o jinou větu, kterou je nutné dokázat zvlášť. To, že u Pythagorovy věty platí obě implikace, je spíše šťastná shoda okolností než pravidlo.

Druhý příklad přímého důkazu je čistě početní a budeme jej za chvíli potřebovat.

Věta 2.24#

Pro každé $n \in \N$ platí: je-li $n$ sudé, je sudé i $n^2$ .

Důkaz

Je-li $n$ sudé, existuje $k \in \N$ takové, že $n = 2k$ . Pak

$n^2 = \left(2k\right)^2 = 4k^2 = 2 \cdot \left(2k^2\right),$

a protože $2k^2 \in \N$ , je číslo $n^2$ sudé.

Nepřímý důkaz

Nabízí se otázka, zda platí i implikace obrácená: plyne ze sudosti čísla $n^2$ sudost čísla $n$ ? Dokázat ji přímo je poměrně nepříjemné – z rovnosti $n^2 = 2m$ se o samotném $n$ snadno nic nedozvíme, odmocnina nás z oboru celých čísel vyvede ven. Zato negace obou výroků jsou velmi konkrétní: „ $n$ je liché“ znamená $n = 2\ell+1$ , a s tím se počítá skvěle.

Věta 2.25#

Pro každé $n \in \N$ platí: je-li $n^2$ sudé, je sudé i $n$ .

Důkaz

Dokážeme obměněnou implikaci, tedy tvrzení „Je-li $n$ liché, je liché i $n^2$ .“. Je-li $n$ liché, existuje $\ell \in \N_0$ takové, že $n = 2\ell+1$ . Pak

$n^2 = \left(2\ell+1\right)^2 = 4\ell^2 + 4\ell + 1 = 2 \cdot \left(2\ell^2 + 2\ell\right) + 1,$

což je zjevně liché číslo. Tím je obměněná implikace dokázána, a musí tedy platit i původní implikace vyslovená větou.

Důsledek 2.26#

Pro každé $n \in \N$ platí: číslo $n$ je sudé právě tehdy, když je sudé číslo $n^2$ .

Důkaz

Implikace „ $\implies$ “ je věta 2.24, implikace „ $\impliedby$ “ je věta 2.25. Platí tedy ekvivalence.

Poznámka 2.27#

Takto se ekvivalence dokazují téměř vždy: rozdělí se na dvě implikace a každá se dokáže zvlášť – klidně jinou metodou, jako právě teď.

Důkaz sporem

Věta 2.28#

Číslo $\sqrt2$ je iracionální, tj. $\sqrt2 \notin \Q$ .

Důkaz

Předpokládejme opak, tedy že $\sqrt2$ je racionální. Pak z definice racionálního čísla existují $p \in \Z$ a $q \in \N$ taková, že

$\sqrt2 = \frac{p}{q},$

přičemž zlomek je v základním tvaru – čísla $p$ a $q$ jsou nesoudělná (kdyby soudělná byla, zlomek bychom rovnou zkrátili). Protože $\sqrt{2} > 0$ , lze navíc předpokládat, že $p \in \N$ .

Umocněním na druhou a vynásobením číslem $q^2$ dostaneme

$p^2 = 2q^2.$

Pravá strana je sudá, a tedy je sudé i číslo $p^2$ ; podle důsledku 2.26 je pak sudé i samo $p$ . Existuje proto $k \in \N$ s vlastností $p = 2k$ . Po dosazení máme

$4k^2 = 2q^2, \qquad \text{tedy} \qquad q^2 = 2k^2.$

Číslo $q^2$ je tedy také sudé a podle téhož důsledku je sudé i $q$ . Čísla $p$ a $q$ jsou tak obě dělitelná dvěma – to je ale spor s předpokladem, že zlomek $\frac{p}{q}$ byl v základním tvaru.

Předpoklad, že $\sqrt2$ je racionální, tedy vede ke sporu. Číslo $\sqrt2$ je proto iracionální.

Poznámka 2.29#

Povšimněme si, jak se v této jediné úvaze potkaly všechny tři metody: přímým důkazem jsme získali větu 2.24, nepřímým větu 2.25, jejich spojením důsledek 2.26 – a ten byl klíčovým krokem důkazu sporem. Matematické texty se zpravidla tvoří přesně takto: jednou dokázané tvrzení se stává nástrojem pro tvrzení další.

Jedna důkazová metoda si zaslouží vlastní podkapitolu. Používá se totiž všude tam, kde dokazujeme tvrzení o všech přirozených číslech najednou nebo o některé jejich nekonečné podmnožině.

Matematická indukce

Řada matematických tvrzení má tvar „Pro každé přirozené číslo $n$ platí $V(n)$ “, kde $V(n)$ je tvrzení závislé na $n$ – tedy výroková forma s parametrem $n \in \N$ . S obecným kvantifikátorem takové tvrzení zkráceně zapíšeme jako

$(\forall n \in \N)\, V(n).$

Příklad 2.30Motivační#

Dokažte, že pro každé $n \in \N$ platí

$1 + 3 + 5 + \ldots + (2n-1) = \sum_{k=1}^n (2k-1) = n^2.$

Pro $n = 1$ , $n = 2$ i $n = 3$ tvrzení ověříme okamžitě, pro $n = 100$ to umíme také – jen to bude zdlouhavé. Jenže přirozených čísel je nekonečně mnoho, a žádný konečný počet ověření proto tvrzení o všech z nich nedokáže. (Konečný je ostatně i čas, který na ověřování máme.) Že nejde o planou obavu, ukazuje následující příklad.

Příklad 2.31#

Uvažujme výrokovou formu $V(n) :=$ „Číslo $n^2+n+41$ je prvočíslo.“ Pro $n = 0$ dostáváme $41$ , pro $n = 1$ číslo $43$ , pro $n = 2$ číslo $47$ – a takto to pokračuje: $V(n)$ platí pro všechna celá $n$ od $0$ do $39$ . Jde o slavný Eulerův polynom, který takto „vyrábí“ prvočísla pro prvních čtyřicet hodnot. Přesto $V(n)$ pro všechna $n$ neplatí, protože

$40^2 + 40 + 41 = 1681 = 41^2.$

Čtyřicet úspěšných pokusů tedy nestačí. Nestačilo by ani čtyřicet miliard.

Tvrzení tohoto typu bychom samozřejmě mohli zkoušet dokazovat přímo – algebraickými úpravami, vhodným rozkladem a podobně. Teď ale hledáme metodu, která si poradí se všemi přirozenými čísly naráz. Opírá se o následující vlastnost množiny $\N$ , kterou zde přijmeme bez důkazu.

Tvrzení 2.32Princip dobrého uspořádání#

Každá neprázdná podmnožina množiny $\N$ má nejmenší prvek.

Věta 2.33Princip matematické indukce#

Nechť $V(n)$ je výroková forma závislá na $n \in \N$ . Pokud

(základ indukce) platí $V(1)$

a
(indukční krok) pro každé $n \in \N$ z platnosti $V(n)$ plyne platnost $V(n+1)$ ,

pak $V(n)$ platí pro každé $n \in \N$ .

Symbolicky psáno:

$\left[V(1) \wedge \bigl((\forall n \in \N)\,(V(n) \implies V(n+1))\bigr)\right] \quad \implies \quad (\forall n \in \N)\, V(n).$

Důkaz

Postupujeme sporem. Předpokládejme, že závěr neplatí, tedy že pro některá přirozená čísla výrok $V(n)$ neplatí. Množina $M$ takových přirozených čísel,

$M := \set{n \in \N \mid \text{výrok } V(n) \text{ neplatí}},$

je pak neprázdná a podle principu dobrého uspořádání má nejmenší prvek; označme jej $n_0$ .

Podle prvního předpokladu platí $V(1)$ , takže $n_0 \neq 1$ , a tedy $n_0 \geq 2$ . Číslo $n_0 - 1$ je proto přirozené a menší než $n_0$ . Protože $n_0$ je nejmenší prvek množiny $M$ , číslo $n_0-1$ do $M$ nepatří, a výrok $V(n_0-1)$ tedy platí. Podle druhého předpokladu (užitého pro $n = n_0-1$ ) z toho plyne platnost $V(n_0)$ – to je ale spor s tím, že $n_0 \in M$ .

Poznámka 2.34#

Princip matematické indukce si dobře představíme jako řadu postavených kostek domina:

Základ indukce $V(1)$ znamená „šťouchneme do prvního kamene a ten spadne“.
Indukční krok $V(n) \implies V(n+1)$ znamená „padne-li $n$ -tý kámen, srazí i $(n+1)$ -ní“.
Závěr $(\forall n \in \N)\, V(n)$ pak znamená „spadnou všechny kameny“.

Obě podmínky indukce jsou nutné. Samotné šťouchnutí nestačí, pokud jsou některé kameny v řadě příliš daleko od sebe, a sebelépe postavená řada nespadne, dokud do prvního kamene někdo nešťouchne.

Označení 2.35#

Předpokladu „platí $V(n)$ “, který v indukčním kroku používáme, se říká indukční předpoklad. Místo ve výpočtu, kde jej použijeme, budeme značit

$\overset{\text{IP}}{=}, \qquad \text{případně} \qquad \overset{\text{IP}}{\leq}, \quad \overset{\text{IP}}{<}.$

Je to dobrý zvyk: čtenář (a u testu opravující) hned vidí, že jste předpoklad skutečně použili – a jak.

Příklad 2.30#

Dokážeme motivační tvrzení z úvodu podkapitoly, tedy že pro každé $n \in \N$ platí

$\sum_{k=1}^n (2k-1) = n^2.$

Základ indukce. Pro $n = 1$ je levá strana rovna $2 \cdot 1 - 1 = 1$ a pravá $1^2 = 1$ . Výrok $V(1)$ tedy platí.

Indukční krok. Nechť pro pevné $n \in \N$ platí $V(n)$ , tj. $\dst \sum_{k=1}^n (2k-1) = n^2$ . Dokážeme $V(n+1)$ , tedy že $\dst \sum_{k=1}^{n+1} (2k-1) = (n+1)^2$ . Poslední sčítanec nové sumy zapíšeme zvlášť a na zbytek použijeme indukční předpoklad:

$\sum_{k=1}^{n+1} (2k-1) = \sum_{k=1}^{n} (2k-1) + \bigl(2(n+1)-1\bigr) \overset{\text{IP}}= n^2 + (2n+1) = (n+1)^2.$

Indukční krok je hotov a podle principu matematické indukce platí $V(n)$ pro každé $n \in \N$ .

Poznámka 2.36#

Povšimněme si struktury důkazu matematickou indukcí, kterou budeme u podobných tvrzení opakovat stále dokola. Poslední člen oddělíme, na zbytek použijeme indukční předpoklad a výsledek upravíme do tvaru, který dostaneme dosazením $n+1$ do dokazovaného vzorce. Vyplatí se cílový tvar napsat dopředu – víte pak, kam se máte dopracovat.

Poznámka 2.37#

Vynechání kterékoliv z obou podmínek činí důkaz bezcenným.

Bez základu indukce: Uvažujme zjevně nepravdivé tvrzení $\dst \sum_{k=1}^n k = \frac{n(n+1)}{2} + 1$ . Indukční krok by prošel bez potíží, neboť

$\sum_{k=1}^{n+1} k = \sum_{k=1}^n k + (n+1) \overset{\text{IP}}= \left(\frac{n(n+1)}{2} + 1\right) + (n+1) = \frac{(n+1)(n+2)}{2} + 1,$

což odpovídá vzorci se záměnou $n$ za $n+1$ .

Tvrzení je přesto nepravdivé pro každé $n$ – neplatí totiž základ indukce, pro $n = 1$ vychází $1 \neq 2$ .
Bez indukčního kroku: Tvrzení „ $n^2+n+41$ je prvočíslo“ základ indukce splňuje (a platí zdaleka nejen pro $n = 1$ ), pravdivé přesto není.

Zkuste si indukci u následujícího příkladu sami.

Příklad 2.38#

Dokažte matematickou indukcí, že pro každé $n \in \N$ platí

$\sum_{k=1}^n k^3 = \left(\frac{n(n+1)}{2}\right)^2 = \left(\sum_{k=1}^n k\right)^2.$

Postup řešení

Základ indukce. Pro $n = 1$ je levá strana rovna $1^3 = 1$ a pravá $\left(\frac{1 \cdot 2}{2}\right)^2 = 1$ .

Indukční krok. Poslední sčítanec oddělíme a na zbytek použijeme indukční předpoklad:

$\begin{aligned} \sum_{k=1}^{n+1} k^3 = \sum_{k=1}^{n} k^3 + (n+1)^3 & \overset{\text{IP}}= \frac{n^2(n+1)^2}{4} + (n+1)^3 = \\ & = (n+1)^2 \cdot \frac{n^2+4n+4}{4} = \left(\frac{(n+1)(n+2)}{2}\right)^2. \end{aligned}$

Tím jsme přesně získali tvar pravé strany dokazované rovnosti pro $n+1$ a důkaz je hotov.

Další příklad ukazuje indukci v úloze na dělitelnost.

Příklad 2.39#

Dokážeme, že číslo $11^{n+1} + 12^{2n-1}$ je dělitelné číslem $133$ pro každé $n \in \N$ .

Základ indukce. Pro $n = 1$ dostáváme $11^2 + 12^1 = 121 + 12 = 133$ , což číslem $133$ dělitelné je.

Indukční krok. Nechť pro jisté $n \in \N$ je číslo $11^{n+1} + 12^{2n-1}$ dělitelné $133$ . Výraz pro $n+1$ upravíme tak, aby se v něm objevil výraz z indukčního předpokladu:

$\begin{aligned} 11^{(n+1)+1} + 12^{2(n+1)-1} & = 11 \cdot 11^{n+1} + 12^2 \cdot 12^{2n-1} = \\ & = 11 \cdot \bigl(11^{n+1} + 12^{2n-1}\bigr) + \underbrace{\bigl(12^2-11\bigr)}_{=133} \cdot 12^{2n-1}. \end{aligned}$

První sčítanec je dělitelný číslem $133$ podle indukčního předpokladu, druhý zjevně také. Součet dvou čísel dělitelných $133$ je jím dělitelný, čímž je krok hotov a celé tvrzení příkladu je dokázáno.

Poznámka 2.40#

Použitý trik se u úloh na dělitelnost opakuje: výraz pro $n+1$ rozdělíme na část, v níž rozpoznáme výraz z indukčního předpokladu, a na zbytek, u něhož dělitelnost ověříme přímo. Prakticky jde o „umělé“ přičtení a odečtení téhož výrazu – zde $11 \cdot 12^{2n-1}$ .

Následující tvrzení si zkuste dokázat sami – postup je stejný jako u sumy, jen se pracuje s rekurentně zadanou posloupností.

Příklad 2.41#

Posloupnost je zadána předpisem

$a_1 = 5, \qquad a_{n+1} = 2a_n - 3 \quad \text{pro každé } n \in \N.$

Dokažte, že pro každé $n \in \N$ platí $a_n = 2^n + 3$ .

Postup řešení

Základ indukce. Pro $n = 1$ dává vzorec $2^1 + 3 = 5$ , což je skutečně $a_1$ .

Indukční krok. Nechť pro jisté $n \in \N$ platí $a_n = 2^n + 3$ . Podle rekurentního předpisu pak

$a_{n+1} = 2a_n - 3 \overset{\text{IP}}= 2\left(2^n + 3\right) - 3 = 2^{n+1} + 6 - 3 = 2^{n+1} + 3,$

což je dokazovaný vzorec pro $n+1$ .

Poznámka 2.42#

U rekurentně zadaných posloupností je indukce zcela přirozená: rekurentní vztah říká právě to, jak se od $n$ -tého členu dostat k $(n+1)$ -nímu – a přesně to indukční krok potřebuje.

Odkud se ale vzorec $a_n = 2^n+3$ vzal? Indukce to neprozradí, ta umí hotový vzorec pouze ověřit. Pomůže si všimnout například toho, že $a_{n+1} - 3 = 2a_n - 6 = 2\left(a_n - 3\right)$ : posloupnost $b_n := a_n - 3$ se tedy v každém kroku zdvojnásobí, a protože $b_1 = 2$ , je $b_n = 2^n$ .

Někdy tvrzení pro malá $n$ neplatí a začít musíme až od jistého $n_0$ . Princip indukce se tím nemění, jen se posune „výchozí kámen domina“.

Věta 2.43Indukce od $n_0$ #

Nechť $n_0 \in \Z$ a nechť $V(n)$ je výroková forma závislá na celém čísle $n \geq n_0$ . Platí-li $V(n_0)$ a plyne-li pro každé celé $n \geq n_0$ z platnosti $V(n)$ platnost $V(n+1)$ , pak $V(n)$ platí pro každé celé $n \geq n_0$ .

Příklad 2.44#

Dokážeme, že pro každé přirozené $n \geq 5$ platí $2^n > n^2$ .

Nejprve si všimněme, proč zrovna od pětky. Pro $n = 1$ nerovnost sice platí ( $2 > 1$ ), ale pro $n = 2$ , $n = 3$ i $n = 4$ neplatí (pro $n = 2$ i $n = 4$ vychází rovnost $4 = 4$ , resp. $16 = 16$ , a pro $n = 3$ je dokonce $8 < 9$ ). Teprve od $n = 5$ platí už vždy – a právě tam musíme umístit základ indukce.

Základ indukce. Pro $n = 5$ je $2^5 = 32 > 25 = 5^2$ .

Indukční krok. Nechť máme jisté $n \geq 5$ a nechť pro něj platí $2^n > n^2$ . Pak

$2^{n+1} = 2 \cdot 2^n \overset{\text{IP}}> 2 \cdot n^2 \overset{?}{\geq} (n+1)^2.$

Zbývá ověřit poslední nerovnost. Roznásobením zjistíme, že je ekvivalentní s $n^2-2n-1 \geq 0$ , tedy s $(n-1)^2 \geq 2$ – a to pro $n \geq 5$ jistě platí.

Poznámka 2.45#

U nerovností se v indukčním kroku postupuje stejně jako u rovností, jen na konci zpravidla zbude ještě pomocná nerovnost, kterou je potřeba dokázat. Otazník nad relací říká, že vztah teprve dokazujeme, a nesmí se s ním proto zacházet jako s hotovým.

Druhý příklad na posunutý začátek je o poznání záludnější – ukazuje, jak se s indukčním předpokladem pracuje u nerovností, kde se s $n$ mění nejen strany nerovnosti, ale i počet sčítanců.

Příklad 2.46#

Označme $\dst S_n := \sum_{k=n+1}^{2n} \frac{1}{k}$ . Dokážeme, že pro každé přirozené $n \geq 2$ platí

$S_n > \frac{13}{24}.$

Na první pohled není jasné, kterým směrem se součet s rostoucím $n$ vyvíjí: sčítanců sice přibývá, ale každý z nich je menší. Ukážeme, že součet roste.

Základ indukce. Pro $n = 2$ je

$S_2 = \frac13 + \frac14 = \frac{7}{12} = \frac{14}{24} > \frac{13}{24}.$

Indukční krok. Nechť máme jisté $n \geq 2$ a nechť pro příslušný součet $S_n$ platí $S_n > \frac{13}{24}$ . Součet $S_{n+1}$ sčítá zlomky $\frac1k$ pro $k$ od $n+2$ do $2n+2$ . Oproti $S_n$ tedy jeden sčítanec ubyl (ten pro $k = n+1$ ) a dva přibyly (pro $k = 2n+1$ a $k = 2n+2$ ):

$S_{n+1} = S_n - \frac{1}{n+1} + \frac{1}{2n+1} + \frac{1}{2n+2}.$

Protože $\frac{1}{n+1} = \frac{2}{2n+2}$ , dva z těchto tří opravných členů se zčásti vyruší:

$S_{n+1} - S_n = \frac{1}{2n+1} + \frac{1}{2n+2} - \frac{2}{2n+2} = \frac{1}{2n+1} - \frac{1}{2n+2} = \frac{1}{\left(2n+1\right)\left(2n+2\right)} > 0.$

Je tedy $S_{n+1} > S_n \overset{\text{IP}}> \frac{13}{24}$ , čímž je indukční krok hotov.

Poznámka 2.47#

Klíčové zde bylo nesrovnávat $S_{n+1}$ přímo s číslem $\frac{13}{24}$ , ale s předchozím součtem $S_n$ . Odhad se tak „sveze“ na indukčním předpokladu, místo aby se počítal znovu od nuly. Tento obrat – dokázat, že je posloupnost rostoucí, a odhadnout jen její první člen – se u nerovností objevuje dost často.

Mimochodem, hodnoty $S_n$ se s rostoucím $n$ blíží k číslu $\ln 2 \doteq 0{,}693$ , zatímco $\frac{13}{24} \doteq 0{,}542$ . Odhad je tedy pohodlný, ale zdaleka ne nejlepší možný; proč tomu tak je, uvidíte v kurzu matematické analýzy.

V indukčním kroku jsme dosud vždy vystačili s platností tvrzení pro jediné předchozí číslo. Někdy je toho ale potřeba více – například u posloupností zadaných rekurentně pomocí několika předchozích členů. Následující verze principu je proto silnější.

Věta 2.48Úplná matematická indukce#

Nechť $V(n)$ je výroková forma závislá na $n \in \N$ . Pokud

platí $V(1)$ a
pro každé $n \in \N$ z platnosti všech výroků $V(1), V(2), \ldots, V(n)$ plyne platnost $V(n+1)$ ,

pak $V(n)$ platí pro každé $n \in \N$ .

Jedním výrokem lze tento princip důkazu zapsat následovně:

$\left[V(1) \wedge \Bigl((\forall n \in \N)\,\bigl(\left(\tblue{(\forall j \in \N, j \leq n)\, V(j)}\right) \implies V(n+1)\bigr)\Bigr)\right] \quad \implies \quad (\forall n \in \N)\, V(n).$

Poznámka 2.49#

Rozdíl oproti „obyčejné“ indukci je jen v síle indukčního předpokladu: místo samotného $V(n)$ smíme použít kterýkoli z výroků $V(1), \ldots, V(n)$ , případně několik z nich nebo dokonce všechny najednou. Důkaz je přitom tentýž jako u věty 2.33 – nejmenší $n_0$ , pro které tvrzení neplatí, opět vede ke sporu.

Příklad 2.50#

Posloupnost je zadána předpisem

$a_1 = 1, \qquad a_2 = 0, \qquad a_{n+2} = 2a_{n+1} + 3a_n \quad \text{pro každé } n \in \N.$

Dokažte, že pro každé $n \in \N$ platí

$a_n = \frac{1}{4}\left(3^{n-1} + 3 \cdot \left(-1\right)^{n-1}\right).$

Postup řešení

Základ indukce. Rekurentní vztah sahá o dva kroky zpět, ověříme proto dva první členy:

$\frac14\left(3^0 + 3 \cdot \left(-1\right)^0\right) = \frac{1+3}{4} = 1 = a_1, \qquad \frac14\left(3^1 + 3 \cdot \left(-1\right)^1\right) = \frac{3-3}{4} = 0 = a_2.$

Indukční krok. Nechť pro jisté $n \in \N$ platí dokazovaný vzorec pro $a_n$ i pro $a_{n+1}$ . Pak

$\begin{aligned} a_{n+2} = 2a_{n+1} + 3a_n & \overset{\text{IP}}= 2 \cdot \frac{1}{4}\left(3^{n} + 3 \cdot \left(-1\right)^{n}\right) + 3 \cdot \frac{1}{4}\left(3^{n-1} + 3 \cdot \left(-1\right)^{n-1}\right) = \\ & = \frac14\left(2 \cdot 3^n + 6 \cdot \left(-1\right)^n + 3^n - 9 \cdot \left(-1\right)^n\right) = \\ & = \frac14\left(3^{n+1} - 3 \cdot \left(-1\right)^n\right) = \frac14\left(3^{n+1} + 3 \cdot \left(-1\right)^{n+1}\right), \end{aligned}$

což je přesně dokazovaný vzorec pro index $n+2$ .

Poznámka 2.51#

Ověřit oba první členy u základu indukce je zde nutné: kdybychom ověřili jen $V(1)$ , indukční krok by neměl z čeho vyjít, protože potřebuje současně $V(n)$ i $V(n+1)$ .

Příklad 2.52#

Dokážeme, že každé přirozené číslo $n \geq 2$ lze zapsat jako součin prvočísel.

Základ indukce. Číslo $2$ je prvočíslo, jde tedy o (jednoprvkový) součin prvočísel.

Indukční krok. Nechť $n \geq 2$ a nechť tvrzení platí pro všechna čísla $2, 3, \ldots, n$ . Uvažujme číslo $n+1$ a rozlišme dva případy:

Je-li $n+1$ prvočíslo, není co dokazovat.
Není-li $n+1$ prvočíslo, má dělitele $d$ s vlastností $1 < d < n+1$ . Pak $n+1 = d \cdot e$ , přičemž i pro druhého činitele platí $1 < e < n+1$ . Obě čísla $d$ , $e$ tedy leží mezi $2$ a $n$ včetně a smíme na ně použít indukční předpoklad – obě jsou součinem prvočísel. Vynásobením obou rozkladů dostáváme rozklad čísla $n+1$ .

Zde už s předpokladem o jediném předchozím čísle nevystačíme: dělitelé $d$ a $e$ mohou být jakákoli čísla menší než $n+1$ , a proto potřebujeme indukci úplnou.

Úplnou indukci si vyzkoušíme ještě jednou, tentokrát na tvrzení, které říká něco netriviálního o prvočíslech. Nechť $p_1 = 2$ , $p_2 = 3$ , $p_3 = 5$ , $p_4 = 7$ , … je posloupnost všech prvočísel uspořádaná podle velikosti.

Příklad 2.53#

Dokážeme, že pro každé $n \in \N$ platí

$p_{n+1} \leq p_1 p_2 \cdots p_n + 1.$

Položme $N := p_1 p_2 \cdots p_n + 1$ . Číslo $N$ je větší než $1$ , a má tedy podle předchozího příkladu nějakého prvočíselného dělitele; označme jej $p$ .

Žádné z prvočísel $p_1, \ldots, p_n$ to být nemůže: každé z nich dělí součin $p_1 \cdots p_n$ , a číslo $N$ proto při dělení jím dává zbytek $1$ . Prvočíslo $p$ je tedy různé od prvních $n$ prvočísel, a protože jsou prvočísla uspořádána podle velikosti, musí být $p \geq p_{n+1}$ . Zároveň $p$ číslo $N$ dělí, takže $p \leq N$ . Celkem

$p_{n+1} \leq p \leq N = p_1 p_2 \cdots p_n + 1.$

Poznámka 2.54#

Jako vedlejší produkt jsme právě dokázali, že prvočísel je nekonečně mnoho: ke každé konečné skupině prvočísel jsme našli další prvočíslo, které v ní není. Jde o jeden z nejstarších důkazů v matematice – pochází z Eukleidových Základů z doby kolem roku 300 př. n. l.

Příklad 2.55#

Dokažte, že pro každé $n \in \N$ platí

$p_n \leq 2^{2^n}.$

Postup řešení

Základ indukce. Pro $n = 1$ je $p_1 = 2 \leq 4 = 2^{2^1}$ .

Indukční krok. Nechť $n \in \N$ a nechť $p_j \leq 2^{2^j}$ pro všechna $j \in \set{1, 2, \ldots, n}$ . Podle předchozího příkladu a indukčního předpokladu je

$p_{n+1} \leq p_1 p_2 \cdots p_n + 1 \overset{\text{IP}}\leq 2^{2^1} \cdot 2^{2^2} \cdots 2^{2^n} + 1 = 2^{2^1 + 2^2 + \ldots + 2^n} + 1 = 2^{2^{n+1}-2} + 1,$

kde jsme v exponentu použili vzorec pro součet geometrické posloupnosti z minulé přednášky, totiž $\dst \sum_{j=1}^n 2^j = 2^{n+1}-2$ .

Zbývá ověřit, že $2^{2^{n+1}-2} + 1 \leq 2^{2^{n+1}}$ . To je snadné: protože $2^{n+1} - 2 \geq 0$ , je $1 \leq 2^{2^{n+1}-2}$ , a tedy

$2^{2^{n+1}-2} + 1 \leq 2 \cdot 2^{2^{n+1}-2} = 2^{2^{n+1}-1} \leq 2^{2^{n+1}}.$

Tím je indukční krok hotov. Povšimněme si, že indukční předpoklad jsme zde potřebovali pro všechna předchozí $j$ najednou – jde tedy skutečně o indukci úplnou.

Poznámka 2.56#

Odhad $p_n \leq 2^{2^n}$ je velmi hrubý: například $p_5 = 11$ , zatímco $2^{2^5} = 2^{32}$ je přes čtyři miliardy. Přesto je cenný – říká, že $n$ -té prvočíslo nemůže růst „jakkoli rychle“, a to je informace, kterou z definice prvočísla vůbec není vidět.

Kombinační čísla a binomická věta

Na závěr si indukci vyzkoušíme na tvrzení, které jsme použili už na konci minulé přednášky, aniž bychom je dokázali.

Definice 2.57Kombinační číslo#

Nechť $n, k \in \N_0$ , $k \leq n$ . Kombinačním číslem $\dbinom{n}{k}$ (čteme „ $n$ nad $k$ “) rozumíme počet všech $k$ -prvkových podmnožin $n$ -prvkové množiny.

Poznámka 2.58#

Ze střední školy víte, že kombinační číslo lze spočítat i vzorcem

$\binom{n}{k} = \frac{n!}{k!\,(n-k)!}.$

Vzorec plyne z kombinatorického pravidla součinu. Speciálně $\binom{n}{0} = \binom{n}{n} = 1$ – prázdnou podmnožinu i celou množinu lze vybrat jediným způsobem.

Věta 2.59Pascalovo pravidlo#

Pro každé $n \in \N_0$ a každé $k \in \N$ takové, že $k \leq n$ , platí

$\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}.$

Důkaz

V $\left(n+1\right)$ -prvkové množině si vyberme a odložme stranou jeden pevný prvek $a$ . Každá $k$ -prvková podmnožina pak patří právě do jedné ze dvou skupin:

podmnožiny obsahující $a$ – zbývajících $k-1$ prvků vybíráme ze zbylých $n$ , takových podmnožin je $\binom{n}{k-1}$ ,
podmnožiny neobsahující $a$ – všech $k$ prvků vybíráme ze zbylých $n$ , takových podmnožin je $\binom{n}{k}$ .

Součet obou počtů dává počet všech $k$ -prvkových podmnožin, tj. $\binom{n+1}{k}$ .

Poznámka 2.60#

Pascalovo pravidlo lze dokázat i přímo, a to úpravou příslušných vzorců s faktoriály podle poznámky 2.58.
Pascalovo pravidlo říká, že každé číslo v Pascalově trojúhelníku je součtem dvou čísel, která stojí přímo nad ním – svých „parůžků“. Právě proto lze trojúhelník sestavovat řádek po řádku – a právě proto je následující věta přirozeným kandidátem na důkaz indukcí.

Věta 2.61Binomická věta#

Pro každé $n \in \N_0$ a každá $a, b \in \R$ platí

$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}.$

(Pro přehlednost zápisu u sum se hodnotou $0^0$ rozumí $1$ , přestože obecně tento výraz není definován.)

Důkaz

Základ indukce. Pro $n = 0$ je pravá strana rovna $\binom{0}{0} a^0 b^{0-0} = 1$ , což se skutečně rovná $(a+b)^0$ .

Indukční krok. Nechť vzorec platí pro jisté $n \in \N_0$ . Pak

$\begin{aligned} (a+b)^{n+1} = (a+b)(a+b)^n & \overset{\text{IP}}= (a+b) \sum_{k=0}^n \binom{n}{k} a^k b^{n-k} = \\ & = \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}. \end{aligned}$

V první sumě posuneme index (přesně tak, jak jsme se to naučili v minulé přednášce): položíme-li $j := k+1$ , projde $j$ hodnoty od $1$ do $n+1$ a dostaneme $\dst \sum_{j=1}^{n+1} \binom{n}{j-1} a^{j} b^{n+1-j}$ . Název indexu můžeme vzápětí vrátit zpět na $k$ . Z obou sum nyní vyjmeme krajní členy tak, aby zbylé členy měly stejný rozsah:

$\begin{aligned} (a+b)^{n+1} & = \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} = \\ & = \underbrace{\binom{n}{n}}_{= 1 = \binom{n+1}{n+1}} a^{n+1} + \sum_{k=1}^{n} \left[\underbrace{\binom{n}{k-1} + \binom{n}{k}}_{= \binom{n+1}{k}}\right] a^k b^{n+1-k} + \underbrace{\binom{n}{0}}_{= 1 = \binom{n+1}{0}} b^{n+1}. \end{aligned}$

Na hranatou závorku použijeme Pascalovo pravidlo (věta 2.59). Protože navíc $\binom{n+1}{n+1} = \binom{n+1}{0} = 1$ , můžeme oba vyjmuté členy vrátit zpět do sumy jako členy pro $k = n+1$ a $k = 0$ :

$(a+b)^{n+1} = \sum_{k=0}^{n+1} \binom{n+1}{k} a^k b^{n+1-k},$

což je dokazovaný vzorec pro $n+1$ .

Důsledek 2.62#

Pro každé $n \in \N$ platí

$\sum_{k=0}^n \binom{n}{k} = 2^n.$

Důkaz

Stačí do binomické věty dosadit $a = b = 1$ .

Poznámka 2.63#

Právě tento vztah jsme bez důkazu použili v posledních příkladech minulé přednášky. Má i názornou interpretaci: levá strana sečte počty podmnožin jednotlivých velikostí, dostáváme tedy počet všech možných podmnožin $n$ -prvkové množiny. Ten je skutečně roven $2^n$ – u každého z $n$ prvků se nezávisle rozhodujeme, zda jej do podmnožiny zařadíme, či nikoli.

Příklad 2.64Když indukce není dobrý pomocník#

Dokážeme, že pro každé $n \in \N$ platí

$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}.$

Tvrzení má právě ten tvar, na jaký jsme u indukce zvyklí: vlevo pěkná suma s $n+1$ sčítanci, vpravo konkrétní upravený výraz. Základ indukce je v pořádku, neboť pro $n = 1$ je $\binom{1}{0}^2 + \binom{1}{1}^2 = 2 = \binom{2}{1}$ . Zkusme nyní indukční krok. Předpokládáme, že

$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$

a chceme odvodit totéž tvrzení pro $n+1$ , konkrétně

$\sum_{k=0}^{n+1} \binom{n+1}{k}^2 = \binom{2n+2}{n+1}.$

Pascalovo pravidlo (věta 2.59) lze použít pro všechna $k \in \set{1, 2, \ldots, n}$ , a tak krajní sčítance $\binom{n+1}{0}^2$ a $\binom{n+1}{n+1}^2$ sumy vlevo, oba rovné jedné dle definice kombinačního čísla, odštěpíme. Dále v každém sčítanci použijeme vzorec $(a+b)^2 = a^2 + 2ab + b^2$ :

$\begin{aligned} \sum_{k=0}^{n+1} \binom{n+1}{k}^2 &= 2 + \sum_{k=1}^n \binom{n+1}{k}^2 = 2 + \sum_{k=1}^n \left[\binom{n}{k} + \binom{n}{k-1}\right]^2 =\\ &= 2 + \sum_{k=1}^n \left[\binom{n}{k}^2 + 2 \binom{n}{k} \binom{n}{k-1} + \binom{n}{k-1}^2\right] =\\ &= 2 + \sum_{k=1}^n \binom{n}{k}^2 + 2 \sum_{k=1}^n \binom{n}{k} \binom{n}{k-1} + \sum_{k=1}^n \binom{n}{k-1}^2. \end{aligned}$

Odštěpenou dvojku teď zpět roztrhneme na dvě jedničky a použijeme je jako chybějící nultý, resp. poslední člen první, resp. třetí sumy. Skutečně, oba tyto členy jsou rovny jedné,

$\binom{n}{0}^2 = 1 \qquad \text{a} \qquad \binom{n}{\left(n+1\right)-1}^2 = \binom{n}{n}^2 = 1,$

a proto dostáváme výraz, ve kterém třetí sumu následně přečíslujeme a zjistíme, že je stejná jako první:

$\sum_{k=0}^n \binom{n}{k}^2 + 2 \sum_{k=1}^n \binom{n}{k} \binom{n}{k-1} + \sum_{k=1}^{n+1} \binom{n}{k-1}^2 = 2\sum_{k=0}^n \binom{n}{k}^2 + 2 \sum_{k=1}^n \binom{n}{k} \binom{n}{k-1}.$

Nakonec použitím indukčního předpokladu získáme tvar

$\sum_{k=0}^{n+1} \binom{n+1}{k}^2 = 2\binom{2n}{n} + 2 \sum_{k=1}^n \binom{n}{k} \binom{n}{k-1}.$

Trojím užitím Pascalova pravidla nyní upravíme pravou stranu dokazované identity:

$\begin{aligned} \binom{2n+2}{n+1} &= \binom{2n+1}{n+1} + \binom{2n+1}{n} =\\ &= \left[\binom{2n}{n+1} + \binom{2n}{n}\right] + \left[\binom{2n}{n} + \binom{2n}{n-1}\right] =\\ &= 2\binom{2n}{n} + \binom{2n}{n+1} + \binom{2n}{n-1} = 2\binom{2n}{n} + 2\binom{2n}{n+1}, \end{aligned}$

kde jsme nakonec využili symetrii kombinačních čísel $\binom{2n}{n-1} = \binom{2n}{n+1}$ . Porovnáním upravené levé a pravé části zjistíme, že indukční krok projde právě tehdy, když

$\sum_{k=1}^{n} \binom{n}{k}\binom{n}{k-1} = \binom{2n}{n+1}.$

A tady se zastavíme. Pokus neskončil chaosem, nýbrž jedinou přesně formulovanou otázkou. Jenže s tou si indukční předpoklad už neporadí. Ten zná hodnotu jedné konkrétní sumy, zatímco my nyní potřebujeme hodnotu sumy jiné, o níž indukční předpoklad nic neříká; navíc se v ní násobí dvě různá kombinační čísla. Jinak řečeno: indukční předpoklad je tvrzení o jednom čísle, o hodnotě součtu, kdežto krok potřebuje vědět, jak je součet vnitřně rozložen mezi jednotlivé sčítance, a to z hodnoty součtu nevyplývá. Dokazované tvrzení není nepravdivé, je jen příliš slabé: nese o sobě méně informace, než jeho vlastní indukční krok potřebuje.

Přímý důkaz původní identity nic z toho nepotřebuje – tentýž počet v něm spočítáme dvěma způsoby. Rozdělme $2n$ -prvkovou množinu $M$ na dvě disjunktní podmnožiny $A$ a $B$ , každou o $n$ prvcích. Je-li $X \subseteq M$ libovolná $n$ -prvková podmnožina a $k = \left|X \cap A\right|$ , pak $\left|X \cap B\right| = n - k$ , a tak lze $X$ jednoznačně sestavit výběrem $k$ prvků z podmnožiny $A$ a $n-k$ prvků z podmnožiny $B$ . Podmnožin $X$ s daným $k$ je proto $\binom{n}{k}\binom{n}{n-k} = \binom{n}{k}^2$ . Číslo $k$ je přitom každou podmnožinou určeno jednoznačně a probíhá hodnoty $0, 1, \ldots, n$ , takže sečtením přes všechny hodnoty $k$ dostaneme počet všech $n$ -prvkových podmnožin množiny $M$ , tj. $\binom{2n}{n}$ .

Poznámka 2.65Vandermondova identita#

Indukce v předchozím příkladu neselhala proto, že by tvrzení neplatilo, ale proto, že jsme ji vedli po příliš slabém tvrzení. Zesílíme-li je přidáním parametrů, indukce projde.

Dohodněme se, že $\binom{n}{k} = 0$ pro $k < 0$ a pro $k > n$ . Odpovídá to kombinatorickému významu, neboť množina o záporném počtu prvků neexistuje a $n$ -prvková množina nemá podmnožinu o více než $n$ prvcích, takže počet takových podmnožin je v obou případech nulový. Při této úmluvě platí Pascalovo pravidlo pro všechna $k \in \Z$ , protože případy, které věta 2.59 nepokrývá, dávají $1 = 1 + 0$ , $1 = 0 + 1$ a $0 = 0 + 0$ . Sumy proto můžeme psát přes všechna celá $k$ a krajní sčítance nás už nemusí zajímat.

Takzvaná Vandermondova identita tvrdí, že pro všechna $m, n \in \N_0$ a všechna $p \in \Z$ platí

$\sum_{k \in \Z} \binom{m}{k}\binom{n}{p-k} = \binom{m+n}{p}.$

V sumě vlevo se sice sčítá přes nekonečnou množinu indexů, nenulových sčítanců je však jen konečně mnoho, neboť je potřeba $0 \leq k \leq m$ .

Toto tvrzení se již dokazuje poměrně snadno, a to indukcí podle $m$ , přičemž $n$ i $p$ zůstávají libovolná. Pro $m = 0$ zůstane ze sumy jediný nenulový sčítanec pro $k = 0$ , rovný $\binom{n}{p}$ . V kroku rozdělíme sumu Pascalovým pravidlem na dvě, na první užijeme indukční předpoklad s hodnotou $p$ a na druhou, po přečíslování $k \mapsto k+1$ , s hodnotou $p-1$ . Součet $\binom{m+n}{p} + \binom{m+n}{p-1}$ je $\binom{m+n+1}{p}$ .

Hlavní rozdíl oproti speciálnímu případu, který jsme se snažili dokázat v příkladu 2.64, je, že indukční předpoklad bude pokrývat i sumy s „posunutými“ členy, které při důkazu indukčního kroku potřebujeme. Volbou $m = n$ a $p = n$ dostaneme původní identitu, volbou $m = n$ a $p = n+1$ pak právě tu hodnotu sumy, na které se indukční krok zastavil. V obou případech užijeme symetrii kombinačních čísel a to, že sčítance mimo příslušný rozsah jsou nulové.

V tomto „zparametrizovaném“ tvaru indukce už projde, přesto není jediná ani nejlepší možnost: přímý důkaz obdobný tomu z příkladu 2.64 dává identitu rovnou, stačí v něm vzít $\left|A\right| = m$ , $\left|B\right| = n$ a vybírat $p$ -prvkové podmnožiny.

Poznámka 2.66#

Ještě dvě poznámky, které se vyplatí mít na paměti.

Indukce je metoda ověřovací: hotový vzorec potvrdí, ale sama o sobě nenapoví, jak k němu dojít. Vzorec pro $\sum_{k=1}^n k^2$ jsme v minulé přednášce odvodili pomocí teleskopické sumy, indukcí bychom jej uměli pouze ověřit. Obě metody se tedy doplňují.
Ne všechno se indukcí dokazovat vyplatí. Některá tvrzení jsou snáze přístupná přímo. Občas se také stane, že indukční krok neprojde ne proto, že by tvrzení neplatilo, ale proto, že je příliš slabé: silnější tvrzení dá silnější indukční předpoklad a krok pak vyjde. Oba tyto případy jsme právě viděli. S některými dalšími podobnými případy se potkáte na cvičeních.

Jedna provokace na závěr

Matematická indukce je mocný nástroj – a jako každý mocný nástroj se dá i zneužít. Následující „důkaz“ je sepsán přesně podle schématu, které jsme si zavedli: má základ indukce, má indukční krok, a přesto dokazuje něco zjevně nesmyslného.

Příklad 2.67Důkaz, který není důkaz#

„Dokážeme“, že všichni studenti Jaderky mají stejné jméno.

Označme $V(n) :=$ „V každé skupině $n$ studentů Jaderky mají všichni studenti stejné jméno.“

Základ indukce. Pro $n = 1$ tvrzení zjevně platí: jednočlenná skupina obsahuje jediného studenta, a všichni v ní tedy mají opravdu stejné jméno.

Indukční krok. Nechť pro jisté $n \in \N$ platí $V(n)$ . Uvažujme libovolnou skupinu $n+1$ studentů a očíslujme je $1, 2, \ldots, n+1$ . Z této skupiny vyberme dvě podskupiny, každou o $n$ studentech (viz obrázek 4):

skupinu $\mathcal{A}$ tvořenou studenty $1, 2, \ldots, n$ ,
skupinu $\mathcal{B}$ tvořenou studenty $2, 3, \ldots, n+1$ .

Obě skupiny mají právě $n$ členů, takže na obě smíme použít indukční předpoklad: uvnitř skupiny $\mathcal{A}$ mají všichni studenti stejné jméno a uvnitř skupiny $\mathcal{B}$ rovněž.

Průnik obou skupin tvoří studenti $2, 3, \ldots, n$ . Zvolme z něj libovolného studenta $s$ . Student $1$ leží spolu se studentem $s$ ve skupině $\mathcal{A}$ , a má tedy stejné jméno jako $s$ . Student $n+1$ leží spolu se studentem $s$ ve skupině $\mathcal{B}$ , a má tedy rovněž stejné jméno jako $s$ . Všichni studenti $1, 2, \ldots, n+1$ se proto jmenují stejně jako $s$ , a tudíž i navzájem stejně. Platí tedy $V(n+1)$ .

Obrázek 4: Skupina $\mathcal{A}$ tvořená studenty $1$ až $n$ a skupina $\mathcal{B}$ tvořená studenty $2$ až $n+1$ . Šedě je vyznačen jejich průnik.

Podle principu matematické indukce platí $V(n)$ pro každé $n \in \N$ . Zvolíme-li speciálně za $n$ počet všech studentů Jaderky, dostáváme, že všichni studenti Jaderky mají stejné jméno.

Závěr je samozřejmě nesmysl – stačí se rozhlédnout po přednáškové místnosti. Základ indukce přitom platí a indukční krok je sepsán podle všech pravidel, která jsme si zavedli. Kde je tedy chyba?

$A$	$B$	$A \land B$	$A \lor B$	$A \implies B$	$A \iff B$
$0$	$0$	$0$	$0$	$1$	$1$
$0$	$1$	$0$	$1$	$1$	$0$
$1$	$0$	$0$	$1$	$0$	$0$
$1$	$1$	$1$	$1$	$1$	$1$

$A$	$B$	$\neg A$	$\neg B$	$A \implies B$	$B \implies A$	$\neg B \implies \neg A$
$0$	$0$	$1$	$1$	$1$	$1$	$1$
$0$	$1$	$1$	$0$	$1$	$0$	$1$
$1$	$0$	$0$	$1$	$0$	$1$	$0$
$1$	$1$	$0$	$0$	$1$	$1$	$1$

$A$	$B$	$A \land B$	$A \lor B$	$A \implies B$	$A \iff B$
$0$	$0$	$0$	$0$	$1$	$1$
$0$	$1$	$0$	$1$	$1$	$0$
$1$	$0$	$0$	$1$	$0$	$0$
$1$	$1$	$1$	$1$	$1$	$1$

$A$	$B$	$\neg A$	$\neg B$	$A \implies B$	$B \implies A$	$\neg B \implies \neg A$
$0$	$0$	$1$	$1$	$1$	$1$	$1$
$0$	$1$	$1$	$0$	$1$	$0$	$1$
$1$	$0$	$0$	$1$	$0$	$1$	$0$
$1$	$1$	$0$	$0$	$1$	$1$	$1$

$A$	$B$	$A \land B$	$A \lor B$	$A \implies B$	$A \iff B$
$0$	$0$	$0$	$0$	$1$	$1$
$0$	$1$	$0$	$1$	$1$	$0$
$1$	$0$	$0$	$1$	$0$	$0$
$1$	$1$	$1$	$1$	$1$	$1$

$A$	$B$	$\neg A$	$\neg B$	$A \implies B$	$B \implies A$	$\neg B \implies \neg A$
$0$	$0$	$1$	$1$	$1$	$1$	$1$
$0$	$1$	$1$	$0$	$1$	$0$	$1$
$1$	$0$	$0$	$1$	$0$	$1$	$0$
$1$	$1$	$0$	$0$	$1$	$1$	$1$