Princip matematické indukce (PMI) se systematicky probírá v jiné části středoškolské matematiky. Na tomto místě je zařazen z důvodu opakování (matka moudrosti) a proto, abychom ji mohli bez uzardění použít při důkazech. Nemám rád, když se článek odvolává na něco, se není dostupné. Hned zkraje poznamenejme, že pro pochopení a používání kombinatoriky není nezbytné znát PMI a umět ji používat v důkazech. Stačí přijmout vlastnosti faktoriálů a kombinačních čísel za své bez důkazu a je to. Takoví studenti mohou tento text opustit a navázat dalším v pořadí. PMI je 5. axiom teorie přirozených čísel (Peanovy axiomy). Protože jde o axiom, nedokazuje se (viz výroková logika). Při formulování axiomů se vychází ze všeobecné zkušenosti. Každé přirozené číslo má svého následníka (tj. číslo o jedna vyšší). PMI vychází ze zkušenosti lineárního uspořádání přirozených čísel. Jestliže nějaké tvrzení platí pro jedničku a dále, z předpokladu, že platí pro číslo k lze dokázat, že platí i pro následníka k+1, bereme za dokázané, věříme (jde o axiom), že tvrzení platí pro všechna přirozená čísla. Jde o řetězení: platí pro 1, když pro 1 tak i pro 1+1=2, když pro 2 tak i pro 3, …. Tento postup se někdy přirovnává k dominu. Obě tyto části jsou totiž podobné dominovému efektu: Spadne první kostka domina. Pokud spadne nějaká kostka domina, spadne i její nejbližší soused. Výsledkem potom je, že spadnou všechny kostky. Zformulujme PMI nyní přesně (v duchu výrokové logiky – jiný kurz tohoto webu):
Princip matematické indukce Nechť V(n) je výroková forma, n N0. Označme P={n N0: V(n)} pravdivostní množinu výrokové formy V(n). Jestliže jsou splněny předpoklady: 1) a N0 : a P (tj. P je neprázdná, tj. existuje nějaké přirozené číslo, které po dosazení do výrokové formy tuto změní v pravdivý výrok) 2) Je-li k N0 pevné číslo k a a zároveň k P, pak také k+1 P pak platí tvrzení: n N0: n a => n P tj. výrokovou formu V(n) splňují všechna přirozená čísla n větší nebo rovna a. Poznámka: N0 je množina přirozených čísel plus 0. Věčné dohady, jestli nula patří do množiny přirozených čísel nemá smysl. Peanovy axiomy platí jak pro množinu N0, tak pro množinu N.
Číslo a je nějaké přirozené číslo. Původně se začínalo 0 resp. 1, ale ukázalo se, že nějaké tvrzení nemusí platit pro prvních pár přirozených čísel, ale počínaje od jistého přirozeného čísla a už platí vždy. Proto tedy ten libovolný začátek. Pro druhou (indukční) část dokazování na základě dlouholeté kantorské zkušenosti doporučuji důsledně používat písmeno k (obecně jiné než n), abychom si tento krok i vizuálně odlišili od tvrzení, kde vystupuje písmeno n. Další zkušenost praví: u 2. kroku si dobře popište co je indukční předpoklad (IP) a co se má dokázat (MD) a teprve pak proveďte vlastní důkaz 2. kroku podle pravidel dokazování matematických tvrzení. Kdybychom si MD nenapsali, často bychom jen tápali do jakého tvaru máme úpravu výrazů dotáhnout. Varování: Žádný krok nelze vynechat A) Když vynecháme 1.krok, můžeme dokázat, že lichá čísla jsou dělitelná 2, tedy tvrzení n N : 2|an , kde an = 2n + 1 hleďte 2.krok IP: nechť tvrzení platí pro k, tj. 2|ak MD: máme dokázat, že platí i pro k+1, tj. 2|ak+1 vlastní důkaz ak+1 = 2(k+1)+1 = 2k + 3 = 2k + 1 + 2 = ak + 2 podle předpokladu je ak dělitelné 2 a 2 je též dělitelná 2 => 2|ak+1 přesto nenajdeme to první číslo
a1=3 a2 = 5 , atp
B) Když vynecháme 2.krok, můžeme dokázat, že číslo 60 je dělitelné všemi přirozenými čísly, tj. tvrzení n N : n|60 1.krok – vyzkoušíme několik prvních přirozených čísel 1|60, 2|60, 3|60, 4|60, 5|60, 6|60 - vše je pravda zkusíme nějaká čísla další čísla namátkou 10|60, 15|60, … to stačí tedy mylně usoudíme, že tvrzení platí ale 7┼60
že by chyba pozorování ?????
Ukažme si několik typických příkladů na důkaz PMI.
Příklad 1: Dokažte, že platí
n N:n
5 => n(n+1) < 2n
Důkaz: Toto tvrzení opravdu neplatí pro 1, 2, 3, 4, jak dosazením zjistíme – ukázka, že se vždycky jedničkou začínat nedá. 1.krok (dělá se vesměs dosazením – pozor na logicky správné dokazování identit, viz výroková logika) n=5 5.6 =30 < 32 = 25 => 5 P (pro n=5 tvrzení platí)
2.krok IP (indukční předpoklad): nechť platí pro k P MD (máme dokázat): (k+1) P vlastní důkaz 2. kroku (k+1)(k+2) = (k+1)k + (k+1)2 < k(k+1) + k(k+1) < 2k + 2k = 2.2k = 2k+1
tj. k(k+1) < 2k tj. (k+l)(k+2) < 2k+1 pouhé roznásobení protože 2
tedy jsme dokázali, že tvrzení platí i pro (k+1) P Jsou tedy splněny předpoklady PMI a dokazovaný výrok je pravdivý v plném rozsahu.
Příklad 2: Dokažte, že platí
n N:n
2 => n < n2
Důkaz: 2 < 4 = 22
1.krok n=2
=>
2.krok IP: nechť platí pro k P MD: (k+1) P vlastní důkaz 2. kroku k+1 < k2 +1 < k2 +2k +1 = (k+1)2
2 P
tj. k < k2 tj. (k+1) < (k+1)2
tedy (k+1) P
podle indukčního předpokladu IP přidání 2k>0 určitě pravou stranu zvýší a použijeme známý vzorec q.e.d
Příklad 3: Dokažte, že platí Bernoulli-ova nerovnost n N : (1+x)n 1 + nx
x <-1, + )
Důkaz: 1.krok
n=1
(1+x)1
1 + 1.x
=>
1 P
2.krok IP: k P tj (1+x)k 1 + kx MD: (k+1) P tj (1+x)k+1 1 + (k+1)x vlastní důkaz 2. kroku (1+x)k+1 = (1+x)k (1+x) vlastnost mocnin (1 + kx)(1+x) použit IP = 1 + kx + x + kx2 roznásobení 1 + (k+1)x tj (k+1) P
Příklad 4: n 2
2n 1
Dokažte, že všechny členy posloupnosti ( 2 3 )1 jsou dělitelné 7. Jinými slovy, máme dokázat, že platí n N : 7|(2n+2 + 32n+1) Důkaz: 1.krok
n=1
(21+2 + 32+1) = 8 + 27 = 35 = 7.5
=>
1 P
2.krok IP: k P tj. 7|ak ak = 2k+2 + 32k+1 MD: (k+1) P tj. 7|ak+1 ak+1 = 2(k+1)+2 + 32(k+1)+1 = 2k+3 + 32k+3 vlastní důkaz 2. kroku ak+1 = 2k+3 + 32k+3 =2.2k+2 + 9.32k+1 = 2(2k+2 + 32k+1) + 7.32k+1 = 2ak + 7.32k+1 tj. (k+1) P
Příklad 5: Dokažte, že součet prvních n přirozených čísel se rovná n(n+1)/2 n N : 1+2+3+4+…+(n-1)+n = n(n+1)/2 Důkaz: 1.krok
n=1
L1 = 1, P1 = 1(1+1)/2 = 1
(L1-levá strana dokazované rovnosti P1- pravá strana dokazované rovnosti)
2.krok IP: k P tj. 1+2+3+…+k = k(k+1)/2 MD: (k+1) P tj. 1+2+3+4+…+k+(k+1) = (k+1)(k+2)/2 vlastní důkaz 2. kroku levá strana dokazované rovnosti (pro k+1) Lk+1 = 1+2+3+…+k+(k+1) = k(k+1)/2 + (k+1) = použit IP = (k+1)(k/2 + 1) = vytknuto (k+1) = (k+1)(k+2)/2 = úprava 2. závorky = Pk+1 což je pravá strana, tedy (k+1) P
Další příklady na dokazování pomocí PMI pro trénink:
n N :n 1
2n
n
n N :n 3
2n
2n 1
n N :n 5
2n
n2
n N :n 1
6 | ( n3 11n)
n
n( n 1)( 2n 1) 6
x2
n N :n 1 x 1 n
n N :n 1
x
n( n 1) 2
3
x 1
n
n N :n 1 x 1
1 2
x
2n
1
n N :n 1
x x 1
2n
n( n 1)( n 2)( n 3) 4 x 1 n 1 n 2n 1 x 1 ( 2 x 1)( 2 x 1) x ( x 1)( x 2)
n
n N :n 1
( 2 x 1)
n2
x 1 n
n N :n 1
2
n
1
n
n N :n 1
2
(2x) x 1
n( n 1)
