Matematická indukce

Matematická indukce je často používaná metoda dokazování v matematice, nejčastěji pokud pracujeme s přirozenými čísly nebo s nějakou jinou posloupností.

Princip

Základním principem je, že dané tvrzení dokážeme pro nějaký první prvek, v přirozených číslech to nejčastěji je n = 1. To dokážeme prostým dosazením. V dalším, indukčním, kroku dokážeme implikaci „pokud tvrzení platí pro n = a, pak platí i pro n = a + 1“.

Z těchto dvou kroků můžeme odvodit, že daný výraz platí pro všechna n (z nějaké množiny, se kterou zrovna pracujeme). Proč tomu tak je? Na začátku si dokážeme, že výraz platí pro n = 1. Zároveň víme, že výraz platí pro n = a a n = a + 1. Zvolíme tak a = 1. Víme, že pro a = 1 výraz platí a také víme, že platí pro a + 1 = 2. V tuto chvíli víme, že výraz platí pro a = 2. Ale protože platí i pro a + 1, musí platit i pro 2 + 1 = 3. A tak dále.

První příklad

První příklad bude triviální. Dokážeme si, že pokud k jakémukoliv sudému číslu přičteme dvojku, dostaneme opět sudé číslo. Protože se pohybujeme v přirozených číslech, zapíšeme obecně sudé číslo jako 2n, kde n je přirozené číslo. Pokud za n dosadíme jakékoliv přirozené číslo, dostaneme ve výsledku sudé číslo, to je vidět na první pohled. Dělitelnost se zapisuje pomocí svislé čáry takto:

$$2\mid2n$$

Tento zápis značí, že dvojka beze zbytku dělí výraz 2n. Když už umíme zapsat dělitelnost, můžeme zapsat i to, co máme matematickou indukcí dokázat.

$$2\mid 2n+2; \quad n\in\mathbb{N}$$

Toto máme v prvním příkladě dokázat, tedy že dvojka dělí výraz 2n + 2 — přesně to odpovídá původnímu slovnímu zadání „pokud k jakémukoliv sudému číslu přičteme dvojku, dostaneme opět sudé číslo“.

V prvním kroku indukce to dokážeme pro první prvek, pro jedničku. Dosadíme do výrazu n = 1:

$$\begin{eqnarray} 2&\mid& 2\cdot1+2\\ 2&\mid& 4 \end{eqnarray}$$

Dvojka dělí čtyřku beze zbytku, takže to pro první prvek platí. Dále přichází na řadu indukční krok, kdy musíme dokázat, že pokud to platí pro a-tý prvek, pak to platí i pro (a + 1) prvek. Na začátku předpokládáme, že platí náš předpoklad, tj n = a:

$$2\mid2a+2$$

O tomto výrazu předpokládáme, že je pravdivý — použijeme ho při konstrukci důkazu. Chceme nyní dokázat, že

$$2\mid2(a+1)+2.$$

Co jsme udělali? Na místo a jsme napsali (a + 1). Důležité jsou ty závorky, tento výraz by byl špatně: 2a + 1 + 2. Nepřičítáme jedničku k celému výrazu, ale opravdu děláme z a výraz o jedničku větší, tj. (a + 1). Výraz upravíme roznásobením závorky.

$$\begin{eqnarray} 2&\mid&2(a+1)+2\\ 2&\mid&2a+2+2
\end{eqnarray}$$

Teď malá odbočka k dělitelnosti. Pokud máme dvě čísla, dejme tomu p a q, která jsou dělitelná nějakým číslem, třeba r, pak platí, že i jejich součet je dělitelný číslem r. Platí tak:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Můžeme si tam dosadit například čísla p = 8, q = 20 a r = 4. Vidíme, že čtyřka dělí jak osmičku, tak dvacítku. A stejně tak dělí i jejich součet 8 + 20 = 28.

Jak toho využijeme v našem příkladu? Rozdělíme si pravou stranu na čísla p a q takto:

$$p=2a+2; \quad q=2$$

Číslo q, tedy dvojka, je triviálně dělitelné dvojkou. A výraz p je také dělitelný dvěma, protože nám to říká předpoklad. Výraz p přesně odpovídá našemu předpokladu, o kterém předpokládáme, že je pravdivý. A pokud je p dělitelné dvěma a zároveň je q dělitelné dvěma, pak je i jejich součet dělitelný dvěma.

Ještě jednou k tomu předpokladu. Na začátku jsme si řekli, že předpokládáme, že platí

$$2\mid2a+2.$$

Proto když jsme během konstrukce důkazu narazili na výraz 2a + 2, mohli jsme o něm říci, že je dělitelný dvěma. Právě proto, že je to náš předpoklad. Toto bývá obyčejně nejtěžší krok matematické indukce — pochopit kdy a pro lze použít indukční předpoklad.

Tímto indukce končí, důkaz byl úspěšně proveden, věta platí.

Pokud byste chtěli, mohli byste to rozložit jinak a nemuseli byste používat předpoklad. p = 2n a q = 2 + 2. Číslo q = 4 je triviálně dělitelné čtyřmi a stejně tak p = 2n, protože po vydělení dvěma nám zůstane číslo n, které je přirozené, tj. celé. Opět jsme tak dostali dva výrazy, které jsou oba dělitelné dvěma, takže i jejich součet je dělitelný dvěma.

V obou případech jsme ale dokázali, že

1. daný výraz platí pro n = 1,

• pokud výraz platí pro n, potom platí i pro n + 1.

Odtud už můžeme odvodit:

• Víme, že výraz platí pro n = 1.
• Pokud platí pro n, musí platit i pro n + 1, tj. i pro 1 + 1, tj. výraz platí i pro n = 2.
• Pokud platí pro n, musí platit i pro n + 1, tj. i pro 2 + 1, tj. výraz platí i pro n = 3.
• Pokud platí pro n, musí platit i pro n + 1, tj. i pro 3 + 1, tj. výraz platí i pro n = 4.
• Pokud platí pro n, musí platit i pro n + 1, tj. i pro 4 + 1, tj. výraz platí i pro n = 5.
• …

Druhý příklad

Dále si matematickou indukcí dokážeme jednoduché tvrzení:

$$2^n\ge2n;\quad n\in\mathbb{N}.$$

Nejprve první krok, zjistíme, jestli tvrzení platí pro n = 1, jakožto první prvek přirozených čísel, ze které n vybíráme.

$$\begin{eqnarray} 2^1&\ge&2\cdot1\\ 2&\ge&2 \end{eqnarray}$$

To triviálně platí. Nyní přejdeme k indukčnímu kroku, ve kterém musíme zjistit, zda když platí pro n = a, jestli se rovná i pro n = a + 1. Takže náš předpoklad je, že platí

$$2^a\ge2a$$

a chceme dokázat:

$$2^{a+1}\ge2(a+1)$$

Levou stranu si nejprve rozepíšeme pomocí pravidel počítání s mocninami a pravou stranu jednoduše roznásobíme.

$$2\cdot2^a\ge2a+2$$

V levé straně místo násobení použijeme sčítání, pravou necháme beze změny.

$$2^a+2^a\ge2a+2$$

Nyní využijeme předpokladu. Předpoklad je výrok, o kterém předpokládáme, že platí. V nerovnici máme na obou stranách po dvou výrazech, které jsou v součtu. Zároveň ale víme, že

$$\begin{eqnarray} 2^a&\ge&2a\\ 2^a&\ge&2. \end{eqnarray}$$

První řádek nám říká předpoklad a druhý výrok je triviální (nejnižší 2^a je pro a = 1 a to se rovná právě dva). Takže víme, že na levé straně jsou oba výrazy větší nebo rovny než oba výrazy na straně pravé. Tím máme indukcí dokázáno, že pokud výraz platí pro a, pak platí i pro (a + 1) a protože výraz platí i pro jedničku, pak je daný výraz pravdivý.

Třetí příklad

Zkusíme si dokázat následující tvrzení:

$$3\mid n\Rightarrow 3\mid n^2;\quad n\in\mathbb{N}$$

Slovně: pokud je n dělitelné třemi, potom je i n² dělitelné třemi. Pokud n není dělitelné třemi, pak výraz triviálně platí (z definice implikace), takže se budeme zabývat případy, kdy je n dělitelné třemi. To nám vygeneruje posloupnost přirozených čísel a_i=3, 6, 9, 12, 15… Od této chvíle se budeme pohybovat v této posloupnosti a_i.

Důkaz indukcí začneme prvním krokem, tj. jestli platí pro první prvek. Připomínám, že se pohybujeme v posloupnosti a_i, takže bereme první prvek této posloupnosti, tj. prvek a₁, což je trojka. Pro trojku výraz platí:

$$3\mid3\Rightarrow 3\mid3^2$$

Nyní přejdeme k indukčnímu kroku. Vidíme, že posloupnost a_i by se dala zapsat jako 3n, kde n je přirozené číslo. Tedy druhý prvek je o tři větší než předchozí atd. Nyní předpokládejme, že výraz platí pro n a musíme zajistit, aby platil i pro (n + 3), což je předpis, který vygeneruje další prvek v posloupnosti, ve které se pohybujeme. Zapíšeme nejprve předpoklad:

$$3\mid n\Rightarrow 3\mid n^2$$

a pak co chceme dokázat

$$3\mid (n+3)\Rightarrow 3\mid(n+3)^2.$$

Rozložíme závorku na druhé straně pomocí vzorce:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

A už jsme skoro v cíli. Na levé straně máme výraz, který je určitě dělitelný třemi, protože n je dle předpokladu dělitelné třemi (pohybujeme se jen v číslech z posloupnosti a_i) a trojka je také dělitelná třemi. Na pravé straně máme nejprve n², což dle předpokladu je dělitelné třemi. Totiž víme, že n je dělitelné třemi a předpoklad říká, že pokud je n dělitelné třemi, pak je i n² dělitelné třemi:

$$3\mid n\Rightarrow 3\mid n^2$$

Dále následuje výraz 6n, který je triviálně dělitelný třemi. Můžete si to představit jako krácení zlomku:

$$\frac{6n}{3}=2n$$

Proměnná n je nějaké přirozené číslo, takže i součin 2n bude přirozené číslo, tj. po dělení trojkou jsme dostali přirozené číslo a výraz 6n tak musí být dělitelný třemi. A devítka na konci je opět dělitelná třemi. Výraz platí pro první prvek i pro indukční krok, je tedy pravdivý.

Počet závorek ve výrazu

Poslední příklad bude trochu netypický. Zkusíme si dokázat tvrzení, že počet závorek v jednoduchém výrazu je vždy sudý, abyste viděli, že matematická indukce lze použít i v úplně jiném kontextu než jen přirozená čísla. Na začátku si musíme definovat, co je to jednoduchý výraz. Jednoduchý výraz je:

• přirozené číslo,
• pokud je p jednoduchý výraz, pak i (p²) je jednoduchý výraz,
• pokud jsou p a q jednoduché výrazy, pak i (p + q) je jednoduchý výraz.

Takže co je jednoduchý výraz: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). A naopak toto nejsou jednoduché výrazy:

• 1 + 2 $\rightarrow$ chybí vnější závorky,
• (1 + 2 $\rightarrow$ chybí pravá závorka,
• 13² $\rightarrow$ chybí vnější závorky,
• (1 + 2 + 3) $\rightarrow$ chybí závorky, správně by zápis měl být (1+(2 + 3))

Jednoduchý výraz může vzniknout například takto. Na začátku si zvolíme jednoduchý výraz (a + b). Nyní za a dosadíme jednoduchý výraz a = (c + d), takže dostaneme ((c + d)+b) a za b dosadíme trojku: ((c + d)+3). Za c dosadíme desítku: ((10 + d)+3) a nakonec za d dosadíme (5²): ((10+(5²))+3). Je důležité dodržovat závorky, jinak to nebude fungovat.

Nyní dokážeme, že jednoduchý výraz obsahuje sudý počet závorek (do sudých čísel spadá i nula).

V prvním kroku indukce si vybereme nějaký první prvek. V tomto případě bude první prvek nejtriviálnější jednoduchý výraz, což je libovolné přirozené číslo. Takže položíme

$$j=n;\quad n\in\mathbb{N}.$$

Pro výraz j platí, že počet závorek je nulový, tedy první prvek vyhovuje. V indukčním kroku budeme předpokládat, že máme dva jednoduché výrazy p a q a že oba mají sudý počet závorek. Pak musíme dokázat, že i jednoduché výrazy (p + q) a (p²) mají sudý počet závorek.

Nejprve sčítání. Zadefinujeme si ještě funkci z(q), která vrací počet závorek výrazu q. Pak platí že výraz (p + q) má z(p)+z(q)+2 závorek. Tedy má o dvě závorky více, než součet závorek výrazů p a q. Dle předpokladu je z(p) i z(q) sudé, tedy pokud sečteme tři sudá čísla, dostaneme opět sudé číslo. Pro tento případ výrok platí.

Teď k mocnině. Opět platí předpoklad, že jednoduchý výraz p obsahuje sudý počet závorek. Výraz (p²) pak obsahuje z(p)+2 závorek, tedy opět o dvě závorky více než výraz p. I v tomto případě sčítáme sudá čísla, výsledek je tak sudý.

Výrok platí pro první prvek a platí i v indukčním kroku, proto je výrok pravdivý.

Další zdroje a příklady

• Spousta příkladů na matematickém fóru
• slajdy na fi.muni.cz [PDF]