´ INDUKCE MATEMATICKA ˇ NEKVINDA ALES
´ indukce 1. Princip matematicke Nechˇt V (n) je nˇejak´a vlastnost pˇrirozen´ ych ˇc´ısel, napˇr. ” n2 + n je dˇeliteln´e n dvˇema ” ˇci ” n < 2 ” atd. M´ame dok´azat tvrzen´ı typu ”Pro kaˇzd´e n ∈ N plat´ı V (n)”. Jedna moˇznost jak to dok´azat je tato: Dok´aˇzeme platnost V (1) a potom dok´aˇzeme pro kaˇzd´e n ∈ N platnost implikace V (n) ⇒ V (n + 1). Pokud jsme toto udˇelali, v´ıme ovˇsem , ˇze plat´ı V (1). Protoˇze plat´ı V (1) ⇒ V (2), plat´ı V (2). Protoˇze plat´ı V (2) ⇒ V (3), plat´ı V (3). Protoˇze plat´ı V (3) ⇒ V (4), plat´ı V (4) atd. Pak tedy vid´ıme, ˇze plat´ı V (n) pro kaˇzd´e n. Symbolicky bychom mohli vyslovit vˇetu: Vˇ eta 1.1. Budˇ M ⊂ N takov´ a, ˇze plat´ı: (i) 1 ∈ M ; (ii) pro kaˇzd´e n ∈ N plat´ı implikace n ∈ M ⇒ n + 1 ∈ M. Pak M = N. ´ pr ˇ´ıklady 2. Jednoduche Pˇ r´ıklad 2.1. Dokaˇzte, ˇze pro kaˇzd´e pˇrirozen´e n plat´ı 1 + 2 + 3 + ··· + n =
1 n(n + 1). 2
ˇ sen´ı. Oznaˇcme L(n) = 1 + 2 + 3 + · · · + n, P (n) = 1 n(n + 1). Reˇ 2 1. Pro n = 1 je to evidentnˇe pravda a plat´ı L(1) = P (1). 2. Pˇredpokl´adejme, ˇze jsme to dok´azali pro n. Dokaˇzme to pro n + 1. L(n + 1) = 1 + 2 + 3 + · · · + n + (n + 1) = L(n) + (n + 1) =indukˇcn´ı pˇredpoklad ¢ 1 1 1¡ = n(n + 1) + n + 1 = n(n + 1) + 2(n + 1) = (n + 1)(n + 2) = P (n + 1). 2 2 2 T´ım je pˇr´ıklad vyˇreˇsen. ¤ Pˇ r´ıklad 2.2. Dokaˇzte, ˇze pro kaˇzd´e pˇrirozen´e n plat´ı 12 + 22 + 32 + · · · + n2 =
1 n(n + 1)(2n + 1). 6
ˇ sen´ı. Oznaˇcme L(n) = 12 + 22 + 32 + · · · + n2 , P (n) = 1 n(n + 1)(2n + 1). Reˇ 6 1. Pro n = 1 je to evidentnˇe pravda a plat´ı L(1) = P (1). 1
ˇ NEKVINDA ALES
2
2. Pˇredpokl´adejme, ˇze jsme to dok´azali pro n. Dokaˇzme to pro n + 1. L(n + 1) = 12 + 22 + 32 + · · · + n2 + (n + 1)2 = L(n) + (n + 1) =indukˇcn´ı pˇredpoklad ¢ 1 1¡ = n(n + 1)(2n + 1) + (n + 1)2 = n(n + 1)(2n + 1) + 6(n + 1)2 6 6 1 1 2 = (n + 1)(2n + n + 6n + 6) = (n + 1)(2n2 + 7n + 6) 6 6 ¡ ¢¡ ¢ 1 1 (n + 1)(n + 2)(2n + 3) = (n + 1) (n + 1) + 1 2(n + 1) + 1 = P (n + 1). 6 6 T´ım je pˇr´ıklad vyˇreˇsen. ¤ Pˇ r´ıklad 2.3. Dokaˇzte, ˇze pro kaˇzd´e pˇrirozen´e n plat´ı 13 + 23 + 33 + · · · + n3 = (1 + 2 + 3 + · · · + n)2 . ˇ sen´ı. Oznaˇcme L(n) = 13 + 23 + 33 + · · · + n3 , P (n) = (1 + 2 + 3 + · · · + n)2 . Reˇ 1. Pro n = 1 je to evidentnˇe pravda a plat´ı L(1) = P (1). 2. Pˇredpokl´adejme, ˇze jsme to dok´azali pro n. Dokaˇzme to pro n + 1. L(n + 1) = 13 + 23 + 33 + · · · + n3 + (n + 1)3 = L(n) + (n + 1)3 =indukˇcn´ı pˇredpoklad ³1 ´2 = (1 + 2 + 3 + · · · + n)2 + (n + 1)3 =dle pˇr´ıkladu 2.1 = n(n + 1) + (n + 1)3 2 ¢ 1 ¡ 2 ¢ ³1 ¢2 1¡ 2 2 3 2 = n (n + 1) + 4(n + 1) = (n + 1) n + 4n + 4 = (n + 1)(n + 2) 4 4 2 ¡ ¢2 =dle pˇr´ıkladu 2.1 = 1 + 2 + 3 + · · · + n + (n + 1) = P (n + 1). T´ım je pˇr´ıklad vyˇreˇsen. ¤ 3n
Pˇ r´ıklad 2.4. Dokaˇzte, ˇze pro kaˇzd´e pˇrirozen´e n nen´ı ˇc´ıslo 2
+3
4n
dˇeliteln´e 73.
ˇ sen´ı. 1. Pro n = 1 je to evidentnˇe pravda neboˇt 23 + 34 = 89 skuteˇcnˇe nen´ı Reˇ dˇeliteln´e 73. 2. Pˇredpokl´adejme, ˇze jsme to dok´azali pro n. Jak je to pro n + 1? Zˇrejmˇe 23(n+1) + 34(n+1) = 8 23n + 81 34n = 8 (23n + 34n ) + 73 34n . Protoˇe 8 (23n + 34n ) nen´ı dˇeliteln´e 73 podle indukˇcn´ıho pˇredpokladu a 73 34n je dˇeliteln´e 73, jejich souˇcet 8 (23n + 34n ) + 73 34n nen´ı dˇeliteln´ y 73. T´ım je pˇr´ıklad vyˇreˇsen. ¤ Poznamenejme k pˇredchoz´ımu pˇr´ıkladu, ˇze pokud bychom se spletli a dok´azali, ˇze pro n = 1 je dan´e ˇc´ıslo dˇeliteln´e 73, pak jsme dok´azali pˇresn´ y opak. Je tedy vidˇet, ˇze 1. indukˇcn´ı krok nelze vynechat. Pˇ r´ıklad 2.5. Je d´ ano n pˇr´ımek v rovinˇe. T´ım se vytvoˇr´ı nˇekolik oblast ’i. Dokaˇzte, ˇ oblast lze obarvit budˇ ˇcervenˇe nebo modˇre tak, ˇze ˇz´ ˇze kadou adn´e dvˇve oblasti se spoleˇcnou hranou nejsou obarveny stejnou barvou. ˇ sen´ı. 1. Pro n = 1 je to evidentnˇe pravda neboˇt 1 pˇr´ımka rozdˇel´ı oblast na Reˇ dvˇe poloroviny a kaˇzdou z nich obarv´ım jednou ze dvou barev. 2. Nechˇt to um´ıme pro n pˇr´ımek a v rovinˇe jich m´am zad´ano n + 1. Pak si jednu odmysl´ıme, nazvˇeme ji p, a dle indukˇcn´ıho pˇredpokladu obarv´ım ty oblasti, kter´e
´ INDUKCE MATEMATICKA
3
tam zbydou. Po pˇrid´an´ı p dostneme nˇejak´e nov´e oblasti, kter´e jsou nicm´enˇe nˇejak obarveny jiˇz z pˇredchoz´ıho kroku. Kaˇzd´a z tˇechto oblast´ı leˇz´ı v jedn´e polorovinˇe od p. Nyn´ı udˇel´ame to, ˇze v jedn´e polorovinˇe od p barvy nech´ame a ve druh´e je vymˇen´ıme. Snadno se nyn´ı uvid´ı, ˇze takto obarven´e oblasti jiˇz nemaj´ı stejnou barvu, pokud maj´ı spoleˇcnou hranu. T´ım jsme udˇelali indukˇcn´ı krok. T´ım je pˇr´ıklad vyˇreˇsen. ¤ 3. Variace na matematickou indukci Nˇekdy se n´am stane, ˇze se podaˇr´ı dok´azat implikaci V (n)&V (n + 1) ⇒ V (n + 2). Staˇc´ı pak uk´azat platnost V (1) a V (2). Form´alnˇe m˚ uˇzeme ps´at: Vˇ eta 3.1. Budˇ M ⊂ N takov´ a, ˇze plat´ı: (i) 1 ∈ M, 2 ∈ M ; (ii) pro kaˇzd´e n ∈ N plat´ı implikace n ∈ M ∧ n + 1 ∈ M ⇒ n + 2 ∈ M. Pak M = N. Pˇ r´ıklad 3.2. Pˇredpokl´ adejme, ˇze cos α = st , s, t ∈ Z. Dokaˇzte, ˇze potom tn cos nα ∈ Z pro kaˇzd´e n ∈ N. ˇ sen´ı. Ovˇeˇrme to nejprve pro n = 1, 2. Reˇ 1. n = 1. Pak m´ame t cos α = t st = s ∈ Z. 2. n = 2. Pak ³ s2 ´ t2 cos 2α = t2 (2 cos2 α − 1) = t2 2 2 − 1 = 2s2 − t2 ∈ Z. t 3. Nechˇt tvrzen´ı plat´ı pro n a n + 1. Tedy pˇredpokl´ad´ame, ˇze tn cos nα ∈ Z a tn+1 cos(n + 1)α ∈ Z. Uˇzit´ım vzorce cos(n + 2)α = 2 cos α cos(n + 1)α − cos nα m´ame tn+2 cos(n + 2)α = 2tn+2 cos α cos(n + 1)α − tn+2 cos nα n+1 = 2 t| cos cos(n + 1)α −t2 t|n cos {z α} |t {z nα} ∈ Z. {z } ∈Z
∈Z
∈Z
¤ ˇ Jin´a varianta je, ˇze se podaˇr´ı dok´azat implikaci: necht plat´ı V (k) pro kaˇzd´e k ≤ n, pak plat´ı V (n + 1). Staˇc´ı pak uk´azat platnost V (1). Prakticky to znamen´a, ˇze pˇri d˚ ukazu V (n + 1) m˚ uˇzeme vyuˇz´ıt jiˇz platn´a tvrzen´ı V (1), V (2), . . . , V (n). Form´alnˇe m˚ uˇzeme ps´at: Vˇ eta 3.3. Budˇ M ⊂ N takov´ a, ˇze plat´ı: (i) 1 ∈ M ; (ii) pro kaˇzd´e n ∈ N plat´ı implikace {1, 2, . . . , n} ⊂ M ⇒ n + 1 ∈ M. Pak M = N. Pˇ r´ıklad 3.4. Pˇredpokl´ adejme, ˇze a ∈ R splˇ nuje a + an + a1n ∈ Z pro kaˇzd´e n ∈ N.
1 a
∈ Z. Dokaˇzte, ˇze potom
ˇ NEKVINDA ALES
4
ˇ sen´ı. 1. Pro n = 1 to pˇredpokl´ad´ame. Reˇ 2. Lze snadno odvodit ³ 1 1 ´³ n 1 ´ ³ 1 ´ an+1 + n+1 = a + a + n − an−1 + n−1 ∈ Z. a | {z a} | {z a } | {z a } ∈Z
∈Z
∈Z
¤ Pˇ r´ıklad 3.5. Na b´ıl´em ˇctvereˇckovan´em pap´ıˇre je n ˇctvereˇck˚ u zaˇcernˇeno. Kaˇzd´y ˇctvereˇcek se pˇrebarv´ı podle n´ asleduj´ıc´ıho pravidla: Kaˇzd´y ˇctvereˇcek z´ısk´ a takovou barvu, jakou mˇela vˇetˇsina z tˇechto tˇr´ı ˇctvereˇck˚ u: uvaˇzovan´y ˇctvereˇcek, ˇctvereˇcek bezprostˇrednˇe od nˇeho vpravo a ˇctvereˇcek bezprostˇrednˇe nad n´ım. Dokaˇzte, ˇze po nejv´yˇse n pˇrebarven´ıch budou vˇsechny ˇctvereˇcky b´ıl´e. ˇ sen´ı. Za dom´ac´ı cviˇcen´ı. Reˇ ¤ Zaj´ımav´ y pˇr´ıklad indukce je v n´asleduj´ıc´ım pˇr´ıkladu. Pˇ r´ıklad 3.6. Nechˇt m, n ∈ N, 1 ≤ m ≤ n. Dokaˇzte, ˇze ³ 1+
1 ´m m m2 <1+ + 2. n n n
ˇ sen´ı. Indukci budeme dˇelat tentokr´at podle m. Fixujme tedy nˇejak´e n ≥ 1. Reˇ 1. Pro m = 1 je to jasn´e. 2. Nechˇt to um´ıme pro nˇejak´e m < n. Dokaˇzme, ˇze pak to plat´ı pro m + 1. Skuteˇcnˇe, ³ 1 ´m+1 ³ 1 ´m ³ 1 ´ indukˇcn´ı pˇredpoklad 1+ = 1+ 1+ < n n n ³ m m2 ´³ 1´ m m2 1 m m2 ≤ 1+ + 2 1+ =1+ + 2 + + 2+ 3 n n n n n n n n m + 1 m2 + m m2 m + 1 (m + 1)2 m2 m+1 =1+ + + = 1 + + + − n n2 n3 n n2 n3 n2 2 m + 1 (m + 1) ≤viz n´ıˇze < 1 + + . n n2 Staˇc´ı dok´azat m2 m+1 − < 0. n3 n2 Ale to je snadn´e. m < n ⇒ m2 < mn ⇒ m2 < mn + n ⇔
m2 m2 m+1 m2 m+1 <m+1 ⇔ 3 < ⇔ − <0 2 3 n n n n n2
T´ım jsme uk´azali, ˇze pro pevn´e n plat´ı tvrzen´ı pro kaˇzd´e 1 ≤ m ≤ n a d˚ ukaz je hotov. ¤
´ INDUKCE MATEMATICKA
5
4. Indukce vyˇ zaduj´ıc´ı vtip Uvedeme si jeden zaj´ımav´ y pˇr´ıklad, ve kter´em na prvn´ı pohled nen´ı jasn´e, jak vlastnˇe indukˇcn´ı krok udˇelat. Pˇ r´ıklad 4.1. Dokaˇzte, ˇze pro kaˇzd´e n ∈ N plat´ı 1 1 1 1 1 + 3 + 3 + ··· + 3 < . 3 2 3 4 n 4 ˇ sen´ı. Nen´ı tˇeˇzk´e dok´azat tuto nerovnost pro n = 1, 2, 3 nebo kolik hodnot Reˇ si zvol´ıme pˇr´ım´ ym v´ ypoˇctem. Pot´ıˇz je udˇelat indukˇcn´ı krok. Jak m´ame usoudit z 1 1 faktu 213 + 313 + 413 + · · · + n13 < 41 , ˇze 213 + 313 + 413 + · · · + n13 + (n+1) z 3 < 4 kdyˇ levou stranu zvˇetˇsujeme a prav´a je poˇr´ad stejn´a? Je nutno zaˇr´ıdit, aby se i prav´a strana mˇenila. To se udˇel´a napˇr. takto: Budeme dokazovat silnˇejˇs´ı tvrzen´ı L(n) =
1 1 1 1 1 1 1 + 3 + 3 + ··· + 3 + ≤ − 2 = P (n), 3 3 2 3 4 n (n + 1) 4 2n
ze kter´eho jiˇz poˇzadovan´a nerovnost snadno plyne. 1. Pro n = 1 plat´ı pˇr´ımo rovnost L(1) = P (1). 2. Nyn´ı udˇel´ame indukˇcn´ı krok. 1 1 1 1 1 1 + 3 + 3 + ··· + 3 + = L(n) + 23 3 4 n (n + 1)3 (n + 1)3 1 1 1 1 1 ≤indukˇcn´ı pˇredpoklad ≤ − 2 + ≤ − , 4 2n (n + 1)3 4 2(n + 1)2
L(n + 1) =
protoˇze 1 1 1 1 1 1 1 1 − 2+ ≤ − ⇔ − 2+ ≤− 3 2 3 4 2n (n + 1) 4 2(n + 1) 2n (n + 1) 2(n + 1)2 1 1 1 1 1 1 ≤ 2− ⇔ ≤ 2− 2(n + 1)2 2n (n + 1)3 (n + 1)3 2n 2(n + 1)2 1 (n + 1)2 − n2 1 2n + 1 ⇔ ≤ ⇔ ≤ ⇔ 2n2 ≤ (n + 1)(2n + 1) 3 (n + 1) 2n2 (n + 1)2 n+1 2n2 ⇔ 2n2 ≤ 2n2 + 3n + 1 coˇz kaˇzd´ y vid´ı a t´ım je d˚ ukaz hotov. ¤ ´ m a geometricky ´ m pr˚ ˇrem a jeho 5. Nerovnost mezi aritmeticky um e aplikace Lemma 5.1 (AG-nerovnost). Nechˇt ai ≥ 0. Pak à n !n n Y 1X ai ≤ (1) ai . n k=1
k=1
Proof. Uˇzit´ım matematick´e indukce podle n. Zaj´ımav´e (a to velmi) je, ˇze se nedaˇr´ı udˇelat indukˇcn´ı krok n ⇒ n + 1. Ale d´a se to udˇelat velmi vtipnˇe n´asleduj´ıc´ım zp˚ usobem. 1. D˚ ukaz je trivi´aln´ı pro n = 1 (i pro n = 2).
ˇ NEKVINDA ALES
6
2. Dok´aˇzeme nejprve implikaci n ⇒ 2n. D´ano 2n ˇc´ısel bi , ci , i = 1, 2, . . . , n i a pouˇzijme (1) pro n ˇc´ısel ai . Uˇzit´ım (1) pro n = 2 m´ame poloˇzme ai = bi +c 2 !2 Ã n !2n ¶2 Ã Y n n µ n Y Y bi + ci 1 X bi + ci bi + ci bi ci ≤ = ≤ 2 2 n 2 k=1 k=1 k=1 k=1 Ã ! 2n n 1 X ≤ (bi + ci ) . 2n k=1
T´ım je krok n ⇒ n − 1 hotov. 3. Dok´aˇzeme nyn´ı implikaci n ⇒ n − 1. Uˇzit´ım (1) pro a1 = a2 = · · · = Pn−1 1 an−1 , an = n−1 ame k=1 ak m´ à ! ( Ãn−1 !)n à !n n−1 n−1 n−1 n−1 Y 1 X 1 X 1 X 1 X ak ak ≤ ak + ak = ak n−1 n n−1 n−1 k=1
k=1
k=1
a tedy n−1 Y
à ak ≤
k=1
k=1
n−1 1 X ak n−1
k=1
!n−1 .
k=1
T´ım je krok n ⇒ n − 1 hotov a AG-nerovnost je dok´az´ana.
¤
Aplikace AG-nerovnosti. Vˇ eta 5.2. Poloˇz
³ ³ 1 ´n 1 ´n+1 an = 1 + , bn = 1 + . n n Pak an je neklesaj´ıc´ı a shora omezen´ a ˇc´ıslem 4, tj. pro kaˇzd´e n ∈ N plat´ı an ≤ an+1 a an ≤ 4 a bn je nerostouc´ı a zdola omezen´ a ˇc´ıslem 2, tj. pro kaˇzd´e n ∈ N plat´ı bn ≥ bn+1 a bn ≤ 2 D˚ ukaz. Dok´aˇzeme, ˇze an je neklesaj´ıc´ı a bn nerostouc´ı. Vyjdeme ze zn´am´e nerovnosti mezi aritmetick´ ym a geometrick´ ym pr˚ umˇerem (jiˇz dok´azan´eho). Pro p1 , p2 , . . . , pk ≥ 0 plat´ı p1 + p2 + · · · + pk √ k (2) p1 p2 . . . pk ≤ . k Uˇzijeme nerovnost (2) pro k = n + 1, p1 = p2 = · · · = pn = 1 + n1 , pn+1 = 1, dostaneme r³ n(1 + n1 ) + 1 n+1+1 1 1 ´n n+1 = =1+ 1+ ≤ n n+1 n+1 n+1 ´ Upravou m´ame ³ 1 ´n ³ 1 ´n+1 1+ ≤ 1+ n n+1 coˇz je tot´eˇz jako an ≤ an+1 . Tedy an je vskutku neklesaj´ıc´ı. Uˇzijme opˇet nerovnost (2) pro k = n + 2, p1 = p2 = · · · = pn = 1+1 1 , pn+2 = 1 a dostaneme n s n+1 + 1 1 1 n+1 1 1+ n n+2 = = 1 n+1 ≤ 1 , n+2 n+2 (1 + n ) 1 + n+1
´ INDUKCE MATEMATICKA
coˇz d´av´a 1 (1 + n1 )n+1
≤
1 (1 +
1 n+2 n+1 )
7
³ 1 ´n+2 1 ´n+1 ³ ≥ 1+ , ⇒ 1+ n n+1
tedy bn ≥ bn+1 a posloupnost bn je vskutku klesaj´ıc´ı. Nyn´ı je zbytek snadn´ y. Volme m, n ∈ N. Pro m ≤ n m´ame am < an < bn , a pro m ≥ n dostaneme am < bm < bn . V kaˇzd´em pˇr´ıpadˇe je am < bn pro libovoln´e m, n ∈ N. Tedy 2 = a1 < bn a am < b1 = 4 a t´ım je dok´az´ana omezenost posloupnost´ı an , bn . ¤ ¡ ¢ 1 n Zaj´ımav´e je, ˇze jsme vlastnˇe dok´azali nerovnost 1 + n ≤ 4. Je ovˇsem dobr´e ¡ ¢n si vˇsimnout, ˇze z pˇr´ıkladu 3.6 dostaneme pro m = n lepˇs´ı odhad 1 + n1 < 3. 6. Dodatek Pˇ r´ıklad 6.1 (Dom´ac´ı kolo MO, 2007). Dokaˇzte, ˇze pro kaˇzd´e n ∈ N existuje a ∈ N, 1 < a < 5n takov´e, ˇze a3 − a + 1 je dˇeliteln´e 5n . N´ avod. 1. Pro n = 1, 2 to lze naj´ıt experiment´alnˇe. To tak´e napov´ı, kdy je a3 − a + 1 dˇeliteln´e 5. 2. Nechˇt pro n m´ame an takov´e, ˇze je a3n − an + 1 = 5n b pro nˇejak´e b. Hledejme nyn´ı ˇc´ıslo k tak, aby pro an+1 := 5n k + an platilo, ˇze a3n+1 − an+1 + 1 je dˇeliteln´e 5n+1 . T´ım se udˇel´a indukˇcn´ı krok. 3. A ˇze an nemus´ı b´ yt menˇs´ı neˇz 5n ? Tak to uˇz je skuteˇcnˇe detail. ¤ References ˇ ´ matemate indukce. Skola mlad´ ych matematik˚ u 40, vydal UV [1] A. Vrba, Princip matematick´ ick´ e olympi´ ady v nakladatelstv´ı Mlad´ a fronta, Praha 1977. Department of Mathematics, Faculty of Civil Engineereng, Czech Technical Univer´ kurova 7, 16629 Prague 6, Czech Republic sity, Tha E-mail address:
[email protected]
