2
D˚ ukazov´ e techniky, Indukce
N´aˇs hlubˇs´ı ´uvod do matematick´ych formalism˚ u pro informatiku zaˇcneme z´akladn´ım pˇrehledem technik matematick´ych d˚ ukaz˚ u. Z nich pro n´as asi nejd˚ uleˇzitˇejˇs´ı je technika d˚ ukaz˚ u matematickou indukc´ı, kter´a je svou podstatou velmi bl´ızk´a poˇc´ıtaˇcov´ym program˚ um (jako iterace cykl˚ u).
2
Struˇ cn´ y pˇrehled lekce * Z´akladn´ı d˚ ukazov´e techniky: pˇr´ım´e, nepˇr´ım´e a sporem. D˚ ukazy tehdy a jen tehdy“. ” * D˚ ukazy matematickou indukc´ı, jejich variace a ´uskal´ı. * Metody zes´ılen´ı tvrzen´ı a rozˇs´ıˇren´ı z´akladu v indukci. Petr Hlinˇ en´ y, FI MU Brno
1
FI: IB000: D˚ ukazy, Indukce
2.1
Pˇrehled z´ akladn´ıch d˚ ukazov´ ych technik
• Pˇr´ım´e odvozen´ı. To je zp˚ usob, o kter´em jsme se dosud bavili.
2
• Kontrapozice (tak´e obr´ acen´ım ˇci nepˇr´ım´y d˚ ukaz). M´ısto vˇety avˇer.“ Jestliˇze plat´ı pˇredpoklady, pak plat´ı z´ ” budeme dokazovat ekvivalentn´ı vˇetu Jestliˇze neplat´ı z´ avˇer, pak neplat´ı alespoˇ n jeden z pˇredpoklad˚ u.“ ” • D˚ ukaz sporem. M´ısto vˇety
2
avˇer.“ Jestliˇze plat´ı pˇredpoklady, pak plat´ı z´ ” budeme dokazovat vˇetu Jestliˇze plat´ı pˇredpoklady a plat´ı opak z´ avˇeru, pak plat´ı opak jednoho ” z pˇredpoklad˚ u (nebo plat´ı jin´e zjevnˇe nepravdiv´e tvrzen´ı).“ 2 • Matematick´a indukce. Pokroˇcil´ a technika. . .
Petr Hlinˇ en´ y, FI MU Brno
2
FI: IB000: D˚ ukazy, Indukce
Pˇr´ıklad d˚ ukazu kontrapozic´ı Definice: Prvoˇc´ıslo p > 1 nem´ a jin´e dˇelitele neˇz 1 a p. Pˇr´ıklad 2.1. na d˚ ukaz kontrapozic´ı (obr´ acen´ım). Vˇ eta. Jestliˇze p je prvoˇc´ıslo vˇetˇs´ı neˇz 2, pak p je lich´e.2 D˚ ukaz: Obr´acen´eho tvrzen´ı – budeme tedy dokazovat, ˇze je-li p sud´e, pak p bud’ nen´ı vˇetˇs´ı neˇz 2, nebo p nen´ı prvoˇc´ıslo. Jsou dvˇe moˇznosti: • p ≤ 2. Pak p nen´ı vˇetˇs´ı neˇz 2.
• p > 2. Pak p = 2 · k pro nˇejak´e cel´e k > 1, tedy p nen´ı prvoˇc´ıslo.
2
2
Pozn´ amka: D˚ ukazy kontrapozic´ı pracuj´ı s negac´ı (opakem) pˇredpoklad˚ u a z´avˇeru. Je-li napˇr. z´avˇer komplikovan´e tvrzen´ı tvaru z toho, ˇze z A a B plyne C, vypl´yv´a, ˇze z A nebo C plyne A a B“, ” nen´ı pouhou intuic´ı snadn´e zjistit, co je vlastnˇe jeho negac´ı. Jak uvid´ıme v pozdˇejˇs´ıch lekc´ıch, uˇzit´ım jednoduch´e induktivn´ı metody lze podobn´a tvrzen´ı negovat zcela mechanicky. Petr Hlinˇ en´ y, FI MU Brno
3
FI: IB000: D˚ ukazy, Indukce
Pˇr´ıklady d˚ ukazu sporem Pˇr´ıklad 2.2. Jin´y pˇr´ıstup k D˚ ukazu 2.1. Vˇ eta. Jestliˇze p je prvoˇc´ıslo vˇetˇs´ı neˇz 2, pak p je lich´e.2 D˚ ukaz sporem: Necht’ tedy p je prvoˇc´ıslo vˇetˇs´ı neˇz 2, kter´e je sud´e. Pak p = 2·k pro nˇejak´e k > 1, tedy p nen´ı prvoˇc´ıslo, spor (s pˇredpokladem, ˇze p je prvoˇc´ıslo). 2 2 Pˇr´ıklad 2.3. √ ˇıslo 2 nen´ı racion´ Vˇ eta. C´ aln´ı.2
√ D˚ ukaz sporem: Necht √’ tedy 2 je racion´aln´ı, tj. necht’ existuj´ı nesoudˇeln´a cel´a kladn´a ˇc´ısla r, s takov´a, ˇze 2 = r/s. 2 – Pak 2 = r2 /s2 , tedy r2 = 2 · s2 , proto r2 je dˇeliteln´e dvˇema. Z toho plyne, ˇze i r je dˇeliteln´e dvˇema (proˇc?). 2 – Jelikoˇz r je dˇeliteln´e dvˇema, je r2 dˇeliteln´e dokonce ˇctyˇrmi, tedy r2 = 4 · m pro nˇejak´e m. Pak ale tak´e 4 · m = 2 · s2 , tedy 2 · m = s2 a proto s2 je dˇeliteln´e dvˇema.2 – Z toho plyne, ˇze s je tak´e dˇeliteln´e dvˇema. Celkem dost´av´ame, ˇze r i s jsou dˇeliteln´e dvˇema, jsou tedy soudˇeln´a a to je spor. 2
2
Nev´ıte-li, jak nˇejakou vˇetu dok´azat, zkuste d˚ ukaz sporem. . .“ ” Petr Hlinˇ en´ y, FI MU Brno
4
FI: IB000: D˚ ukazy, Indukce
2.2
Vˇ ety typu tehdy a jen tehdy“ ”
• Uvaˇzujme nyn´ı (v matematice pomˇernˇe hojn´e) vˇety tvaru Necht’ plat´ı pˇredpoklady P. Pak tvrzen´ı A plat´ı tehdy a jen tehdy, ” plat´ı-li tvrzen´ı B.“ 2 • Pˇr´ıklady jin´ych formulac´ı t´eˇze vˇety jsou: ∗ Za pˇredpoklad˚ u P je tvrzen´ı B nutnou a postaˇcuj´ıc´ı podm´ınkou pro platnost tvrzen´ı A.2 ∗ Za pˇredpoklad˚ u P je tvrzen´ı A nutnou a postaˇcuj´ıc´ı podm´ınkou pro platnost tvrzen´ı B.2 ∗ Necht’ plat´ı pˇredpoklady P. Pak tvrzen´ı A plat´ı pr´avˇe tehdy kdyˇz plat´ı tvrzen´ı B.2 • D˚ ukaz vˇet tohoto tvaru m´ a vˇzdy dvˇe ˇc´ asti(!). Je tˇreba dok´azat:
∗ Jestliˇze plat´ı pˇredpoklady P a tvrzen´ı A, pak plat´ı tvrzen´ı B. ∗ Jestliˇze plat´ı pˇredpoklady P a tvrzen´ı B, pak plat´ı tvrzen´ı A.
Petr Hlinˇ en´ y, FI MU Brno
5
FI: IB000: D˚ ukazy, Indukce
2.3
Matematick´ a indukce
• Jde o d˚ ukazovou techniku aplikovatelnou na tvrzen´ı tohoto typu: Pro kaˇzd´e pˇrirozen´e (cel´e) n ≥ k0 plat´ı T (n).“ ” Zde k0 je nˇejak´e pevn´e pˇrir. ˇc´ıslo a T (n) je tvrzen´ı parametrizovan´e ˇc´ıs. n.2 Pˇr´ıkladem je tˇreba tvrzen´ı: Pro kaˇzd´e n ≥ 0 plat´ı, ˇze n pˇr´ımek dˇel´ı rovinu nejv´yˇse na 12 n(n + 1) + 1 oblast´ı.2 • Princip matematick´ e indukce ˇr´ık´ a (coby axiom), ˇze k d˚ ukazu vˇety Pro kaˇzd´e pˇrirozen´e (cel´e) n ≥ k0 plat´ı T (n).“ ” staˇc´ı ovˇeˇrit platnost tˇechto dvou tvrzen´ı: ∗ T (k0 )
(tzv. b´aze neboli z´aklad indukce)
∗ Pro kaˇzd´e n ≥ k0 ; jestliˇze plat´ı T (n), pak plat´ı tak´e T (n + 1).
(indukˇcn´ı pˇredpoklad) (indukˇcn´ı krok)2
• Pozor, v tomto pˇredmˇ etu poˇ c´ıt´ ame 0 za pˇrirozen´ eˇ c´ıslo! Petr Hlinˇ en´ y, FI MU Brno
6
FI: IB000: D˚ ukazy, Indukce
Pˇr´ıklady d˚ ukaz˚ u indukc´ı Pˇr´ıklad 2.5. Velmi jednoduch´ a a pˇr´ımoˇcar´ a indukce. Vˇ eta. Pro kaˇzd´e n ≥ 1 je stejn´ a pravdˇepodobnost, ˇze pˇri souˇcasn´em hodu n kostkami bude v´ysledn´y souˇcet sud´y, jako, ˇze bude lich´y. 2 D˚ ukaz: Z´aklad indukce je zde zˇrejm´y: Na jedn´e kostce (poctiv´e!) jsou tˇri lich´a a tˇri sud´a ˇc´ısla, takˇze obˇe skupiny padaj´ı se stejnou pravdˇepodobnost´ı. 2 Indukˇcn´ı krok pro n ≥ 1: Necht’ psn pravdˇepodobnost, ˇze pˇri hodu n kostkami bude v´ysledn´y souˇcet sud´y, a pln je pravdˇepodobnost lich´eho. Podle indukˇcn´ıho pˇredpokladu je psn = pln = 12 . 2 Hod’me nav´ıc (n + 1)-n´ı kostkou. Podle toho, zda na n´ı padne lich´e nebo sud´e ˇc´ıslo, je pravdˇepodobnost celkov´eho sud´eho souˇctu rovna 3 l 3 1 pn + psn = 6 6 2 a stejnˇe pro pravdˇepodobnost celkov´eho lich´eho souˇctu.
Petr Hlinˇ en´ y, FI MU Brno
7
FI: IB000: D˚ ukazy, Indukce
2
Pˇr´ıklad 2.6. Uk´azka d˚ ukazov´e s´ıly“ principu matematick´e indukce. ” Vˇ eta. Pro kaˇzd´e n ≥ 0 plat´ı, ˇze n pˇr´ımek dˇel´ı rovinu nejv´yˇse na 1 n(n + 1) + 1 2
oblast´ı.
D˚ ukaz: 2Pro b´azi indukce staˇc´ı, ˇze 0 pˇr´ımek dˇel´ı rovinu na jednu ˇc´ast. (Vˇsimnˇete si tak´e, ˇze 1 pˇr´ımka dˇel´ı rovinu na dvˇe ˇc´ asti, jen pro lepˇs´ı pochopen´ı d˚ ukazu.) Mˇejme nyn´ı rovinu rozdˇelenou n pˇr´ımkami na nejv´yˇse 12 n(n + 1) + 1 ˇc´ast´ı.2 Dalˇs´ı, (n + 1)-n´ı pˇr´ımka je rozdˇelena pr˚ useˇc´ıky s pˇredchoz´ımi pˇr´ımkami na nejv´yˇse n + 1 u ´sek˚ u a kaˇzd´y z nich oddˇel´ı novou ˇc´ ast roviny. 2Celkem tedy bude rovina rozdˇelena naˇsimi pˇr´ımkami na nejv´yˇse tento poˇcet oblast´ı: 1 1 1 1 n(n + 1)+1+ (n+1) = n(n + 1)+ ·2(n+1)+ 1 = (n + 1)(n + 2) + 1 2 2 2 2 2 Petr Hlinˇ en´ y, FI MU Brno
8
FI: IB000: D˚ ukazy, Indukce
Pˇr´ıklad 2.7. Dalˇs´ı indukˇcn´ı d˚ ukaz rozepsan´y v podrobn´ych kroc´ıch. P Vˇ eta. Pro kaˇzd´e n ≥ 0 plat´ı nj=0 j = n(n+1) .2 2 D˚ ukaz indukc´ı vzhledem k n. • B´aze: Mus´ıme dok´ azat tvrzen´ı T (0), coˇz je v tomto pˇr´ıpadˇe rovnost P0 0(0+1) . Tato rovnost (zjevnˇe) plat´ı.2 j=0 j = 2 • Indukˇcn´ı krok: Mus´ıme dok´ azat n´ asleduj´ıc´ı tvrzen´ı: Jestliˇze plat´ı
Pi
j=0 j
Pˇredpokl´adejme tedy, ˇze Pi+1 (i+1)(i+1+1) = j=0 j = 2 i+1 X j=0
j =
i X j=0
j +(i+1) =
=
Pi
i(i+1) 2
j=0 j
kde i ≥ 0, pak plat´ı
=
(i+1)(i+2) . 2
i(i+1) 2
Pi+1
j=0 j
=
(i+1)(i+2) .2 2
a pokusme se dok´azat, ˇze pak tak´e
To uˇz plyne u ´pravou:
i(i + 1) i(i + 1) + 2(i + 1) (i + 1)(i + 2) +(i+1) = = 2 2 2 2
Podle principu matematick´e indukce je cel´y d˚ ukaz hotov. Petr Hlinˇ en´ y, FI MU Brno
9
FI: IB000: D˚ ukazy, Indukce
2
2.4
Koment´ aˇre k matematick´ e indukci
Pro spr´avn´e a u ´spˇeˇsn´e pouˇzit´ı indukce v dokazov´ an´ı je vhodn´e si zapamatovat nˇekolik cenn´ych rad: • Z´akladn´ı trik vˇsech d˚ ukaz˚ u matematickou indukc´ı je vhodn´a reformulace tvrzen´ı T (n + 1) tak, aby se odvol´ avalo“ na tvrzen´ı T (n). ” ∗ Dobˇre se vˇzdy pod´ıvejte, v ˇcem se liˇs´ı tvrzen´ı T (n + 1) od tvrzen´ı T (n). Tento rozd´ıl“ budete muset v d˚ ukaze zd˚ uvodnit. 2 ” • Pozor, obˇcas je potˇreba zes´ılit“ tvrzen´ı T (n), aby indukˇcn´ı krok spr´avnˇe ” fungoval“.2 ” ˇ se chybuje v d˚ ukazu indukˇcn´ıho kroku, nebot’ ten b´yv´a vˇetˇsinou • Casto v´yraznˇe obt´ıˇznˇejˇs´ı neˇz b´ aze, ale o to zr´adnˇejˇs´ı jsou chyby v samotn´e zd´ anlivˇe snadn´e b´azi! ∗ Dejte si dobr´y pozor, od kter´e hodnoty n ≥ k0 je indukˇcn´ı krok univerz´alnˇe platn´y. . .
Petr Hlinˇ en´ y, FI MU Brno
10
FI: IB000: D˚ ukazy, Indukce
Pˇr´ıklad 2.8. Kdyˇz je nutno indukˇcn´ı krok zes´ılit. . . Vˇ eta. Pro kaˇzd´e n ≥ 1 plat´ı s(n) =
1 1 1 1 + + + ··· + < 1. 1·2 2·3 3·4 n(n + 1)
1 D˚ ukaz:2 B´aze indukce je zˇrejm´ a, nebot’ 1·2 < 1. Co vˇsak indukˇcn´ı krok? Pˇredpoklad s(n) < 1 je s´ am o sobˇe pˇr´ıliˇs slab´y“ na ” 1 to, aby bylo moˇzno tvrdit s(n + 1) = s(n) + (n+1)(n+2) < 1. 2
Neznamen´a to jeˇstˇe, ˇze by tvrzen´ı nebylo platn´e, jen je potˇreba n´aˇs indukˇcn´ı pˇredpoklad zes´ılit. Budeme dokazovat Pro kaˇzd´e pˇrirozen´e n ≥ 1 plat´ı s(n) ≤ 1 − ”
1 n+1
< 1 .“ 2
To plat´ı pro n = 1 a d´ale uˇz u ´pravou jen dokonˇc´ıme zes´ılen´y indukˇcn´ı krok: s(n + 1) = s(n) +
1 1 1 ≤ 1− + = (n + 1)(n + 2) n + 1 (n + 1)(n + 2)
= 1+ Petr Hlinˇ en´ y, FI MU Brno
−(n + 2) + 1 1 = 1− (n + 1)(n + 2) n+2 11
FI: IB000: D˚ ukazy, Indukce
2
Rozˇs´ıˇren´ı b´ aze a pˇredpokladu Mimo zesilov´an´ı tvrzen´ı indukˇcn´ıho kroku jsme nˇekdy okolnostmi nuceni i k rozˇsiˇrov´an´ı samotn´e b´aze indukce a s n´ı indukˇcn´ıho pˇredpokladu na v´ıce neˇz jednu hodnotu parametru n. 2 – M˚ uˇzeme napˇr´ıklad pˇredpokl´ adat platnost (parametrizovan´ych) tvrzen´ı T (n) i T (n + 1) z´aroveˇ n, a pak odvozovat platnost T (n + 2). Toto lze samozˇrejmˇe zobecnit na jak´ykoliv poˇcet pˇredpokl´adan´ych parametr˚ u. 2 – M˚ uˇzeme dokonce pˇredpokl´ adat platnost tvrzen´ı T (j) pro vˇsechna j = k0 , k0 + 1, . . . , n najednou a dokazovat T (n + 1). (Toto typicky vyuˇzijeme v pˇr´ıpadech, kdy indukˇcn´ı krok rozdˇel´ı“ probl´em ” T (n + 1) na dvˇe menˇs´ı ˇc´ asti a z nich pak odvod´ı platnost T (n + 1).) 2 Fakt: Obˇe prezentovan´a rozˇs´ıˇren´ı“ jsou v koneˇcn´em d˚ usledku jen speci´aln´ımi ” instancemi z´akladn´ı matematick´e indukce; pouˇzit´e rozˇs´ıˇren´e moˇznosti pouze zjednoduˇsuj´ı form´aln´ı z´apis d˚ ukazu. Petr Hlinˇ en´ y, FI MU Brno
12
FI: IB000: D˚ ukazy, Indukce
Pˇr´ıklad 2.9. Kdyˇz je nutno rozˇs´ıˇrit b´ azi a indukˇcn´ı pˇredpoklad. . . Vˇ eta. Necht’ funkce f pro kaˇzd´e n ≥ 0 splˇ nuje vztah f (n + 2) = aroveˇ n f (1) = 2, tak plat´ı 2f (n + 1) − f (n). Pokud plat´ı f (0) = 1 a z´ f (n) = n + 1 pro vˇsechna pˇrirozen´ a n ≥ 0. 2 D˚ ukaz: Uˇz samotn´y pohled na dan´y vztah f (n + 2) = 2f (n + 1) − f (n) naznaˇcuje, ˇze bychom mˇeli rozˇs´ıˇrit indukˇcn´ı pˇredpoklad (a krok) zhruba takto: n plat´ı Pro kaˇzd´e n ≥ 0; jestliˇze plat´ı T (n); neboli f (n) = n + 1, a z´aroveˇ T (n + 1); f (n + 1) = n + 2, pak plat´ı tak´e T (n + 2); f (n + 2) = n + 3. B´ aze indukce –2 pozor, zde uˇz mus´ıme ovˇeˇrit dvˇe hodnoty f (0) = 0 + 1 = 1,
f (1) = 1 + 1 = 2 .2
N´ aˇs indukˇcn´ı krok tak nyn´ı m˚ uˇze vyuˇz´ıt cel´eho rozˇs´ıˇren´eho pˇredpokladu, znalosti hodnot f (n) i f (n + 1), pro ovˇeˇren´ı f (n + 2) = 2f (n + 1) − f (n) = 2 · (n + 1 + 1) − (n + 1) = n + 3 = n + 2 + 1 . 2 Jak by tento d˚ ukaz mˇel b´yt formulov´an v tradiˇcn´ı“ indukci? 2( Substituc´ı“.) ” ” Petr Hlinˇ en´ y, FI MU Brno
13
FI: IB000: D˚ ukazy, Indukce
Z´ avˇ erem mal´ y probl´ em“ ” Pˇr´ıklad 2.10. Aneb jak snadno lze v matematick´e indukci udˇelat chybu. Vˇ eta. ( nevˇeta“) ” V kaˇzd´em st´adu o n ≥ 1 kon´ıch maj´ı vˇsichni konˇe stejnou barvu.2 D˚ ukaz indukc´ı vzhledem k n. B´ aze: Ve st´adu o jednom koni maj´ı vˇsichni konˇe stejnou barvu.2 Indukˇcn´ı krok: Necht’ S = {K1 , . . . , Kn+1 } je st´ ado o n + 1 kon´ıch. Dok´aˇzeme, ˇze vˇsichni konˇe maj´ı stejnou barvu. Uvaˇzme dvˇe menˇs´ı st´ada: – S ′ = {K1 , K2 , . . . , Kn }
– S ′′ = {K2 , . . . , Kn , Kn+1 }
2
Podle indukˇcn´ıho pˇredpokladu maj´ı vˇsichni konˇe ve st´adu S ′ stejnou barvu B ′ . Podobnˇe vˇsichni konˇe ve st´ adu S ′′ maj´ı podle indukˇcn´ıho pˇredpokladu stejnou ′′ barvu B . 2Dok´aˇzeme, ˇze B ′ = B ′′ , tedy ˇze vˇsichni konˇe ve st´adu S maj´ı stejnou barvu. To ale plyne z toho, ˇze konˇe K2 , . . . , Kn patˇr´ı jak do st´ada S ′ , tak i do st´ada S ′′ . 2 2 Ale to uˇz je podvod! Vid´ıte, kde? Petr Hlinˇ en´ y, FI MU Brno
14
FI: IB000: D˚ ukazy, Indukce
