Příručka důkazů

Příklad

Chceme-li dokázat, že součet dvou lichých čísel je sudé číslo, bude začátek a konec vypadat takto:

Příklad

Chceme-li dokázat, že \sqrt{2} je iracionální, šablona pro důkaz bude vypadat takto:

Příklad

Pokud dokazujeme jako v předchozím kroku, že součet dvou lichých čísel je sudé číslo, po sepsání začátku a konce budeme pokračovat tím, že si z definice rozepíšeme, co znamená, že je číslo liché/sudé:

Všimněte si, že při každém rozepsání z definice jsme použili jiné písmeno, protože zatím nevíme, jaký je vztah mezi k,l,m.

Nyní již můžeme snadno důkaz dokončit. Stačí si všimnout, že a+b=2k+1+2l+1=2k+2l+2. To chceme, aby se rovnalo 2m, kde m je celé číslo, takže stačí zvolit m≔k+l+1. Tím máme hotový důkaz.

Příklad

Podívejme se, jak bude po rozepsání z definice vypadat šablona pro důkaz, že \sqrt{2} je iracionální:

V tomto případě již nelze důkaz hned přímočaře dokončit, přesto jsme se ale posunuli o krok blíž.

Příklad

Chceme odvodit vzoreček pro pravděpodobnost, že nastanou dva nezávislé jevy.

Vyzkoušíme to na příkladu: Jaká je pravděpodobnost, že hodím-li dvěma mincemi, padnou dvě hlavy? Sestavíme si tabulku všech možností:

Máme čtyři možné případy a jen jeden z nich je vyhovující, takže pravděpodobnost je \frac{1}{4}. Z toho zatím není úplně zřejmé, jaký to má vztah k pravděpodobnosti \frac{1}{2}, že na každé jednotlivé minci padne hlava. Zkusíme jiný příklad: hodíme dvěma kostkami a budeme sledovat, jestli na první padne 3 a na druhé 5.

Pravděpodobnost hodu trojky na jedné kostce je \frac{1}{6}, stejně tak pětky.

Příznivý jev (hod trojky a pětky) je jen jeden, ale všech jevů máme 36. Tedy pravděpodobnost je \frac{1}{36}.

Z těchto dvou příkladů už je vidět, že by se mohlo jednat o součin jednotlivých pravděpodobností. Ovšem v obou příkladech byly obě vstupní pravděpodobnosti stejné. Bylo by tedy dobré pro jistotu vyzkoušet příklad, kde jsou různé. Zkusme najít pravděpodobnost, že na první kostce padne sudé číslo a na druhé 1.

Dohromady máme 3 příznivé jevy a všech jevů je 36, tedy pravděpodobnost je \frac{3}{36}=\frac{1}{12}. Zato vezmeme-li si tyto jevy zvlášť, pravděpodobnost prvního je \frac{1}{2} a druhého \frac{1}{6}. To souhlasí s naší hypotézou, že se jedná o součin. Nyní již nastane čas ověřit hypotézu nějak rigorózněji.

Příklad

Zkusíme dokázat důležitý vzorec

Dosaďme například n=3. Potom dostáváme

Vynásobíme obě strany rovnosti 1-q:

Roznásobíme výraz na levé straně, abychom ověříli, že se rovná výrazu na pravé straně:

Vidíme, že členy se stejnou mocninou se vždy vzájemně vyruší a zbyde jen první a poslední. Zároveň si můžeme všimnout, že to takto bude fungovat pro libovolné n, což nám silně napovídá, jak provést obecný důkaz.

Příklad

Zkusme najít vzorec pro součet prvních několika lichých čísel. Spočteme si

V tom už je vidět vzor – součet prvních n lichých čísel se rovná n^2. To můžeme následně dokázat například pomocí matematické indukce.

Příklad

V sekci Konkrétní příklady jsme si všimli vzoru, že součet prvních n lichých čísel se rovná n^2. Z následujícího obrázku je dobře vidět, proč to tak funguje:

Příklad

Jedním ze známých problémů je rozklad kladného celého čísla n na součet kladných celých čísel. Můžeme zkusit dokázat, že počet takových rozkladů, kde nejvyšším číslem je číslo k, je stejný jako počet rozkladů obsahujících právě k sčítanců.

Hlavní myšlenkou takového důkazu je nakreslit si obrázek, z kterého to již snadno vyplyne. Vezmeme např. číslo 9 a napíšeme si ho jako 4+3+2 (sčítance píšeme vždy v sestupném pořadí), kde je nejvyšším číslem 4. To můžeme nakreslit jako tři řádky, první sestávající ze čtyř čtverečků, druhý ze tří a poslední ze dvou:

Pokud se nyní podíváme na sloupce, vidíme, že počty čtverečků odpovídají rozkladu sestávajícímu ze čtyř sčítanců: 9=3+3+2+1. Právě proto, že nejdelší je 4, vždycky dostaneme čtyři řádky, tedy rozklad na čtyři sčítance.

Stejně tak můžeme argumentovat naopak, máme-li čtyři sloupce, dostaneme alespoň jeden řádek obsahující 4 (a žádný větší). Máme tedy jednoznačné přiřazení mezi rozklady s nejvyšším sčítancem 4 a rozkladem na 4 sčítance, z čehož plyne, že je jich stejně. Analogicky to samozřejmě funguje i pro jiná čísla n a k.

Příklad

Zkusme najít výherní strategii pro piškvorky 3\times 3. Možných posloupností tahů je 9\cdot 8\cdot 7\cdot \cdots \cdot 2\cdot 1=362880, takže kdybychom je všechny procházeli postupně, trvalo by to hodně dlouho. Naštěstí ale z devíti možných počátečních tahů stačí uvažovat jen tři, protože ostatní jsou symetrické:

Po každém z těchto tahů by mohlo následovat osm dalších, ale s ohledem na symetrii máme dohromady jen dvanáct:

U každé z těchto pozic už dokážeme snadno určit, jak dopadne.

Příklad

Máme-li například kubickou rovnici, je často vhodné tipnout si řešení. Pokud jej najdeme, můžeme si problém zredukovat na snazší a ten pak vyřešit.

Mějme rovnici x^3+x^2-x-1=0. Podle základní věty algebry víme, že platí x^3+x^2-x-1=(x-a)\cdot (x-b)\cdot (x-c), kde a,b,c jsou kořeny rovnice. Zkusíme nějaký z nich uhodnout. Můžeme vyzkoušet, jestli je řešením třeba nula nebo jednička – a jednička je opravdu řešením. To znamená, že můžeme rovnici vydělit (x-1), čímž dostaneme x^2+2x+1=0. U toho již snadno najdeme dva zbylé kořeny.