2 Důkazové techniky, Indukce
Náš hlubší úvod do matematických formalismů pro informatiku začneme základním
přehledem technik matematických důkazů. Z nich pro nás asi nejdůležitější je technika
důkazů matematickou indukcí, která je svou podstatou velmi blízká počítačovým
programům (jako iterace cyklů).
Stručný přehled lekce
* Základní důkazové techniky: přímé, nepřímé a sporem.
Důkazy ,,tehdy a jen tehdy".
* Důkazy matematickou indukcí, jejich variace a úskalí.
* Metody zesílení tvrzení a rozšíření základu v indukci.
Petr Hliněný, Fl MU Brno 1 IB000 "Úv. Inf.": Důkazy, Indukce
2.1 Přehled základních důkazových technik
* Přímé odvození. To je způsob, o kterém jsme se dosud bavili.
D
etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Důkazy, Indukce
2.1 Přehled základních důkazových technik
* Přímé odvození. To je způsob, o kterém jsme se dosud bavili.
* Kontrapozice (také obrácením či nepřímý důkaz). Místo věty
,,Jestliže platí předpoklady, pak platí závěr."
budeme dokazovat ekvivalentní větu
,,Jestliže neplatí závěr, pak neplatí alespoň jeden z předpokladů."
>etr Hliněný, Fl MU Brnc X)0 "Úv. Inf.": Důkazy, Indukce
2.1 Přehled základních důkazových technik
* Přímé odvození. To je způsob, o kterém jsme se dosud bavili.
* Kontrapozice (také obrácením či nepřímý důkaz). Místo věty
,,Jestliže platí předpoklady, pak platí závěr."
budeme dokazovat ekvivalentní větu
,,Jestliže neplatí závěr, pak neplatí alespoň jeden z předpokladů."
* Důkaz sporem. Místo věty
,,Jestliže platí předpoklady, pak platí závěr."
budeme dokazovat větu
,,Jestliže platí předpoklady a platí opak závěru, pak platí opak jednoho
z předpokladů (nebo platí jiné zjevně nepravdivé tvrzení)."
D
etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Důkazy, Indukce
2.1 Přehled základních důkazových technik
* Přímé odvození. To je způsob, o kterém jsme se dosud bavili.
* Kontrapozice (také obrácením či nepřímý důkaz). Místo věty
,,Jestliže platí předpoklady, pak platí závěr."
budeme dokazovat ekvivalentní větu
,,Jestliže neplatí závěr, pak neplatí alespoň jeden z předpokladů."
* Důkaz sporem. Místo věty
,,Jestliže platí předpoklady, pak platí závěr."
budeme dokazovat větu
,,Jestliže platí předpoklady a platí opak závěru, pak platí opak jednoho
z předpokladů (nebo platí jiné zjevně nepravdivé tvrzení)."
* Matematická indukce. Pokročilá technika...
D
etr Hliněný, Fl MU Brno IB000 "Úv. Inf.": Důkazy, Indukce
Příklad důkazu kontrapozicí
Definice: Prvočíslo p > 1 nemá jiné dělitele než lap.
Příklad 2.1. na důkaz kontrapozicí (obrácením).
Věta. Jestliže p je prvočíslo větší než 2, pak p je liché.
D
etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Důkazy, Indukce
Príklad důkazu kontrapozici
Definice: Prvočíslo p > 1 nemá jiné dělitele než lap.
Příklad 2.1. na důkaz kontrapozicí (obrácením).
Věta. Jestliže p je prvočíslo větší než 2, pak p je liché.
Důkaz: Obráceného tvrzení- budeme tedy dokazovat, že je-li p sudé, pak p
buď není větší než 2, nebo p není prvočíslo. Jsou dvě možnosti:
* p < 2. Pak p není větší než 2.
* p > 2. Pak p = 2.k pro nějaké celé k > 1, tedy p není prvočíslo.
>etr Hliněný, Fl MU Brnc X)0 "Úv. Inf.": Důkazy, Indukce
Příklad důkazu kontrapozicí
Definice: Prvočíslo p > 1 nemá jiné dělitele než lap.
Příklad 2.1. na důkaz kontrapozicí (obrácením).
Věta. Jestliže p je prvočíslo větší než 2, pak p je liché.
Důkaz: Obráceného tvrzení- budeme tedy dokazovat, že je-li p sudé, pak p
buď není větší než 2, nebo p není prvočíslo. Jsou dvě možnosti:
* p < 2. Pak p není větší než 2.
* p > 2. Pak p = 2.k pro nějaké celé k > 1, tedy p není prvočíslo.
D
Poznámka: Důkazy kontrapozicí pracují s negací (opakem) předpokladů a závěru. Je-li
např. závěr komplikované tvrzení tvaru
,,z toho, ze z A a B plyne C vyplývá, ze z A nebo C plyne A a B " ,
není pouhou intuicí snadné zjistit, co je vlastně jeho negací. Jak uvidíme v pozdějších
lekcích, užitím jednoduché induktivní metody lze podobná tvrzení negovat zcela
mechanicky.
Petr Hliněný, Fl MU Brno IB000 "Úv. Inf.": Důkazy, Indukce
Příklady důkazu sporem
Příklad 2.2. Jiný přístup k Důkazu
Důkaz sporem: Nechť tedy p je prvočíslo větší než 2, které je sudé. Pak p = 2-k
pro nějaké k > 1, tedy p není prvočíslo, spor (s předpokladem, že p je prvočíslo).
D
etr Hliněný, Fl MU Brno 4 IB000 "Uv. Inf.": Důkazy, Indukce
Příklady důkazu sporem
Příklad 2.2. Jiný přístup k Důkazu
Důkaz sporem: Nechť tedy p je prvočíslo větší než 2, které je sudé. Pak p = 2-k
pro nějaké k > 1, tedy p není prvočíslo, spor (s předpokladem, že p je prvočíslo).
D
Příklad 2.3.
Věta. Číslo \/2 není racionální.
D
etr Hliněný, Fl MU Brno 4 IB000 "Uv. Inf.": Důkazy, Indukce
Příklady důkazu sporem
Příklad 2.2. Jiný přístup k Důkazu
Důkaz sporem: Nechť tedy p je prvočíslo větší než 2, které je sudé. Pak p = 2-k
pro nějaké k > 1, tedy p není prvočíslo, spor (s předpokladem, že p je prvočíslo).
D
Příklad 2.3.
Věta. Číslo \/2 není racionální.
Důkaz sporem: Nechť tedy A/2 je racionální, tj. nechť existují nesoudělná celá kladná
čísla r, s taková, že A/2 = r/s.
D
etr Hliněný, Fl MU Brno 4 IB000 "Uv. Inf.": Důkazy, Indukce
Příklady důkazu sporem
Příklad 2.2. Jiný přístup k Důkazu
Důkaz sporem: Nechť tedy p je prvočíslo větší než 2, které je sudé. Pak p = 2-k
pro nějaké k > 1, tedy p není prvočíslo, spor (s předpokladem, že p je prvočíslo).
D
Příklad 2.3.
Věta. Číslo \/2 není racionální.
Důkaz sporem: Nechť tedy A/2 je racionální, tj. nechť existují nesoudělná celá kladná
čísla r, s taková, že A/2 = r/s.
- Pak 2 = r2
/s2
, tedy r2
= 2 ˇ s2
, proto r2
je dělitelné dvěma. Z toho plyne, že i r
je dělitelné dvěma (proč?).
D
etr Hliněný, Fl MU Brno 4 IB000 "Uv. Inf.": Důkazy, Indukce
Příklady důkazu sporem
Příklad 2.2. Jiný přístup k Důkazu
Důkaz sporem: Nechť tedy p je prvočíslo větší než 2, které je sudé. Pak p = 2-k
pro nějaké k > 1, tedy p není prvočíslo, spor (s předpokladem, že p je prvočíslo).
D
Příklad 2.3.
Věta. Číslo \/2 není racionální.
Důkaz sporem: Nechť tedy A/2 je racionální, tj. nechť existují nesoudělná celá kladná
čísla r, s taková, že A/2 = r/s.
- Pak 2 = r2
/s2
, tedy r2
= 2 ˇ s2
, proto r2
je dělitelné dvěma. Z toho plyne, že i r
je dělitelné dvěma (proč?).
- Jelikož r je dělitelné dvěma, je r2
dělitelné dokonce čtyřmi, tedy r2
= 4 ˇ m pro
nějaké m. Pak ale také 4 - m = 2- s2
, tedy 2 - m = s2
a proto s2
je dělitelné dvěma.
D
etr Hliněný, Fl MU Brno 4 IB000 "Uv. Inf.": Důkazy, Indukce
Příklady důkazu sporem
Příklad 2.2. Jiný přístup k Důkazu
Důkaz sporem: Nechť tedy p je prvočíslo větší než 2, které je sudé. Pak p = 2-k
pro nějaké k > 1, tedy p není prvočíslo, spor (s předpokladem, že p je prvočíslo).
D
Příklad 2.3.
Věta. Číslo \/2 není racionální.
Důkaz sporem: Nechť tedy A/2 je racionální, tj. nechť existují nesoudělná celá kladná
čísla r, s taková, že A/2 = r/s.
- Pak 2 = r2
/s2
, tedy r2
= 2 ˇ s2
, proto r2
je dělitelné dvěma. Z toho plyne, že i r
je dělitelné dvěma (proč?).
- Jelikož r je dělitelné dvěma, je r2
dělitelné dokonce čtyřmi, tedy r2
= 4 ˇ m pro
nějaké m. Pak ale také 4 - m = 2- s2
, tedy 2 - m = s2
a proto s2
je dělitelné dvěma.
- Z toho plyne, že s je také dělitelné dvěma. Celkem dostáváme, že r i s jsou dělitelné
dvěma, jsou tedy soudělná a to je spor.
D
etr Hliněný, Fl MU Brno 4 IB000 "Uv. Inf.": Důkazy, Indukce
Příklady důkazu sporem
Příklad 2.2. Jiný přístup k Důkazu
Důkaz sporem: Nechť tedy p je prvočíslo větší než 2, které je sudé. Pak p = 2-k
pro nějaké k > 1, tedy p není prvočíslo, spor (s předpokladem, že p je prvočíslo).
D
Příklad 2.3.
Věta. Číslo \/2 není racionální.
Důkaz sporem: Nechť tedy A/2 je racionální, tj. nechť existují nesoudělná celá kladná
čísla r, s taková, že A/2 = r/s.
- Pak 2 = r2
/s2
, tedy r2
= 2 ˇ s2
, proto r2
je dělitelné dvěma. Z toho plyne, že i r
je dělitelné dvěma (proč?).
- Jelikož r je dělitelné dvěma, je r2
dělitelné dokonce čtyřmi, tedy r2
= 4 ˇ m pro
nějaké m. Pak ale také 4 - m = 2- s2
, tedy 2 - m = s2
a proto s2
je dělitelné dvěma.
- Z toho plyne, že s je také dělitelné dvěma. Celkem dostáváme, že r i s jsou dělitelné
dvěma, jsou tedy soudělná a to je spor.
,,Nevíte-li, jak nějakou větu dokázat, zkuste důkaz sporem. .. "
D
etr Hliněný, Fl MU Brno 4 IB000 "Uv. Inf.": Důkazy, Indukce
2.2 Věty typu ,,tehdy a jen tehdy"
* Uvažujme nyní (v matematice poměrně hojné) věty tvaru
,,Nechť platí předpoklady P. Pak tvrzení A platí tehdy a jen tehdy,
platí-li tvrzení B."
D
etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Důkazy, Indukce
2.2 Věty typu ,,tehdy a jen tehdy'
ˇ
ˇ
Uvažujme nyní (v matematice poměrně hojné) věty tvaru
,,Nechť platí předpoklady P. Pak tvrzení A platí tehdy a jen tehdy,
platí-li tvrzení B."
Příklady jiných formulací téže věty jsou:
* Za předpokladů P je tvrzení B nutnou a postačující podmínkou pro
platnost tvrzení A.
D
etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Důkazy, Indukce
2.2 Věty typu ,,tehdy a jen tehdy"
* Uvažujme nyní (v matematice poměrně hojné) věty tvaru
,,Nechť platí předpoklady P. Pak tvrzení A platí tehdy a jen tehdy,
platí-li tvrzení B."
* Příklady jiných formulací téže věty jsou:
* Za předpokladů P je tvrzení B nutnou a postačující podmínkou pro
platnost tvrzení A.
* Za předpokladů P je tvrzení A nutnou a postačující podmínkou pro
platnost tvrzení B.
D
etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Důkazy, Indukce
2.2 Věty typu ,,tehdy a jen tehdy"
* Uvažujme nyní (v matematice poměrně hojné) věty tvaru
,,Nechť platí předpoklady P. Pak tvrzení A platí tehdy a jen tehdy,
platí-li tvrzení B."
* Příklady jiných formulací téže věty jsou:
* Za předpokladů P je tvrzení B nutnou a postačující podmínkou pro
platnost tvrzení A.
* Za předpokladů P je tvrzení A nutnou a postačující podmínkou pro
platnost tvrzení B.
* Nechť platí předpoklady P. Pak tvrzení A platí právě tehdy když platí
tvrzení B.
D
etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Důkazy, Indukce
2.2 Věty typu ,,tehdy a jen tehdy"
* Uvažujme nyní (v matematice poměrně hojné) věty tvaru
,,Nechť platí předpoklady P. Pak tvrzení A platí tehdy a jen tehdy,
platí-li tvrzení B."
* Příklady jiných formulací téže věty jsou:
* Za předpokladů P je tvrzení B nutnou a postačující podmínkou pro
platnost tvrzení A.
* Za předpokladů P je tvrzení A nutnou a postačující podmínkou pro
platnost tvrzení B.
* Nechť platí předpoklady P. Pak tvrzení A platí právě tehdy když platí
tvrzení B.
* Důkaz vět tohoto tvaru má vždy dvě části(l). Je třeba dokázat:
* Jestliže platí předpoklady P a tvrzení A, pak platí tvrzení B.
* Jestliže platí předpoklady P a tvrzení B, pak platí tvrzení A.
D
etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Důkazy, Indukce
2.3 Matematická indukce
* Jde o důkazovou techniku aplikovatelnou na tvrzení tohoto typu:
,,Pro každé přirozené (celé) n > ko platí Tin)."
Zde ko je nějaké pevné přir. číslo a T(n) je tvrzení parametrizované čís. n.
D
etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Důkazy, Indukce
2.3 Matematická indukce
* Jde o důkazovou techniku aplikovatelnou na tvrzení tohoto typu:
,,Pro každé přirozené (celé) n> ko platí Tin)."
Zde ko je nějaké pevné přir. číslo a T(n) je tvrzení parametrizované čís. n.
Příkladem je třeba tvrzení:
Pro každé n > 0 platí, že n přímek dělí rovinu
nejvýše na \nin + 1) + 1 oblastí.
>etr Hliněný, Fl MU Brnc X)0 "Úv. Inf.": Důkazy, Indukce
2.3 M a t e m a t i c k á indukce
* Jde o důkazovou techniku aplikovatelnou na tvrzení tohoto typu:
,,Pro každé přirozené (celé) n> ko platíT(n)."
Zde ko je nějaké pevné přir. číslo a T(n) je tvrzení parametrizované čís. n.
Příkladem je třeba tvrzení:
Pro každé n > 0 platí, že n přímek dělí rovinu
nejvýše na \nin + 1) + 1 oblastí.
* Princip matematické indukce říká (coby axiom), že k důkazu věty
,,Pro každé přirozené (celé) n > ko platí Tin)."
stačí ověřit platnost těchto dvou tvrzení:
* T (ho) (tzv. báze neboli základ indukce)
* Pro každé n > ko; jestliže platí T(n), (indukční předpoklad)
pak platí také T(n + 1). (indukční krok)
D
etr Hliněný, Fl MU Brno IB000 "Úv. Inf.": Důkazy, Indukce
2.3 M a t e m a t i c k á indukce
* Jde o důkazovou techniku aplikovatelnou na tvrzení tohoto typu:
,,Pro každé přirozené (celé) n> ko platíT(n)."
Zde ko je nějaké pevné přir. číslo a T(n) je tvrzení parametrizované čís. n.
Příkladem je třeba tvrzení:
Pro každé n > 0 platí, že n přímek dělí rovinu
nejvýše na \nin + 1) + 1 oblastí.
* Princip matematické indukce říká (coby axiom), že k důkazu věty
,,Pro každé přirozené (celé) n > ko platí Tin)."
stačí ověřit platnost těchto dvou tvrzení:
* T (ho) (tzv. báze neboli základ indukce)
* Pro každé n > ko; jestliže platí T(n), (indukční předpoklad)
pak platí také T(n + 1). (indukční krok)
* Pozor, v tomto předmětu počítáme 0 za přirozené číslo!
^etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Důkazy, Indukce
Příklady důkazů indukcí
Příklad 2.4. Velmi jednoduchá a přímočará indukce.
Věta. Pro každé n > 1 je stejná pravděpodobnost, že při současném hodu
n kostkami bude výsledný součet sudý, jako, že bude lichý.
D
etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Důkazy, Indukce
Príklady důkazu indukci
Příklad 2.4. Velmi jednoduchá a přímočará indukce.
Věta. Pro každé n > 1 je stejná pravděpodobnost, že při současném hodu
n kostkami bude výsledný součet sudý, jako, že bude lichý.
Důkaz: Základ indukce je zde zřejmý: Na jedné kostce (poctivé!) jsou tři lichá
a tři sudá čísla, takže obě skupiny padají se stejnou pravděpodobností.
>etr Hliněný, Fl MU Brnc X)0 "Úv. Inf.": Důkazy, Indukce
Příklady důkazů indukcí
Příklad 2.4. Velmi jednoduchá a přímočará indukce.
Věta. Pro každé n > 1 je stejná pravděpodobnost, že při současném hodu
n kostkami bude výsledný součet sudý jako, že bude lichý.
Důkaz: Základ indukce je zde zřejmý: Na jedné kostce (poctivé!) jsou tři lichá
a tři sudá čísla, takže obě skupiny padají se stejnou pravděpodobností.
Indukční krok pro n > 1: Nechť ps
n pravděpodobnost, že při hodu n kostkami
bude výsledný součet sudý, a pl
n je pravděpodobnost lichého. Podle indukčního
předpokladu je ps
n = pl
n = \.
D
etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Důkazy, Indukce
Příklady důkazů indukcí
Příklad 2.4. Velmi jednoduchá a přímočará indukce.
Věta. Pro každé n > 1 je stejná pravděpodobnost, že při současném hodu
n kostkami bude výsledný součet sudý jako, že bude lichý.
Důkaz: Základ indukce je zde zřejmý: Na jedné kostce (poctivé!) jsou tři lichá
a tři sudá čísla, takže obě skupiny padají se stejnou pravděpodobností.
Indukční krok pro n > 1: Nechť ps
n pravděpodobnost, že při hodu n kostkami
bude výsledný součet sudý, a pl
n je pravděpodobnost lichého. Podle indukčního
předpokladu je ps
n = pl
n = \.
Hoďme navíc (n + l)-ní kostkou. Podle toho, zda na ní padne liché nebo sudé
číslo, je pravděpodobnost celkového sudého součtu rovna
3 , 3 a 1
a stejně pro pravděpodobnost celkového lichého součtu. n
D
etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Důkazy, Indukce
Příklad 2.5. Ukázka důkazové ,,síly" principu matematické indukce.
Věta. Pro každé n > O platí, že n přímek dělí rovinu nejvýše na
1
-n{n+ 1) + 1
oblastí.
Důkaz:
D
etr Hliněný, Fl MU Brno 000 "Ův. Inf.": Důkazy, Indukce
Příklad 2.5. Ukázka důkazové ,,síly" principu matematické indukce.
Věta. Pro každé n > O platí, že n přímek dělí rovinu nejvýše na
1
-n{n+ 1) + 1
oblastí.
Důkaz: Pro bázi indukce stačí, že 0 přímek dělí rovinu na jednu část. (Všimněte
si také, že 1 přímka dělí rovinu na dvě části, jen pro lepší pochopení důkazu.)
Mějme nyní rovinu rozdělenou n přímkami na nejvýše | n ( n + l) + l částí. Další,
(n + l)-ní přímka je rozdělena průsečíky s předchozími přímkami na nejvýše
n + 1 úseků a každý z nich oddělí novou část roviny.
D
etr Hliněný, Fl MU Brno 000 "Ův. Inf.": Důkazy, Indukce
Příklad 2.5. Ukázka důkazové ,,síly" principu matematické indukce.
Věta. Pro každé n > O platí, že n přímek dělí rovinu nejvýše na
1
oblastí.
-n{n+ 1) + 1
Důkaz: Pro bázi indukce stačí, že 0 přímek dělí rovinu na jednu část. (Všimněte
si také, že 1 přímka dělí rovinu na dvě části, jen pro lepší pochopení důkazu.)
Mějme nyní rovinu rozdělenou n přímkami na nejvýše | n ( n + l) + l částí. Další,
(n + l)-ní přímka je rozdělena průsečíky s předchozími přímkami na nejvýše
n + 1 úseků a každý z nich oddělí novou část roviny. Celkem tedy bude rovina
rozdělena našimi přímkami na nejvýše tento počet částí:
1
n(n + l) + l + (n+l)
1 , x 1 ,
-n(n + l) + --2(n+l) + l
1
(n + l)(n + 2) + l
D
D
etr Hliněný, Fl MU Brno 000 "Úv. Inf.": Důkazy, Indukce
Příklad 2.6. Další indukční důkaz rozepsaný v podrobných krocích.
^n ˇ _ n(n+
-3=0 J -- 2Věta. Pro každé n > O platiJ2TM=0j - ^ 
D
etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Důkazy, Indukce
Příklad 2.6. Další indukční důkaz rozepsaný v podrobných krocích.
Věta. Pro každé n > O platíJ2]=0j = ^2H.
Důkaz indukcí vzhledem k n.
* Báze: Musíme dokázat tvrzení T(0), což je v tomto případě rovnost
Yfj=oJ = 2 ˇ "'"ato r o v n o s t
(zjevně) platí.
>etr Hliněný, Fl MU Brnc X)0 "Úv. Inf.": Důkazy, Indukce
Příklad 2.6. Další indukční důkaz rozepsaný v podrobných krocích.
Věta. Pro každé n > O platíJ2]=0j = ^2H.
Důkaz indukcí vzhledem k n.
* Báze: Musíme dokázat tvrzení T(0), což je v tomto případě rovnost
Yfj=oJ = 2 ˇ "'"ato r o v n o s t
(zjevně) platí.
* Indukční krok: Musíme dokázat následující tvrzení:
Jestliže platí Y^j^j = ^ ^ kde i > 0, pak platí'E^oi = ( m )
2
( i + 2 )
.
>etr Hliněný, Fl MU Brno IB000 "Úv. Inf.": Důkazy, Indukce
Příklad 2.6. Další indukční důkaz rozepsaný v podrobných krocích.
^n ˇ _ n(n+
-3=0 J -- 2Věta. Pro každé n > O platiJ2TM=0j - ^ 
Důkaz indukcí vzhledem k n.
* Báze: Musíme dokázat tvrzení T(0), což je v tomto případě rovnost
-o ˇ _ 0(0+
-3=0 J -- 2Yfj=oJ = 2 ˇ "'"ato r o v n o s t
(zjevně) platí.
* Indukční krok: Musíme dokázat následující tvrzení:
Jestliže platí '  5 = 0 j = í o
ř i kde i
> °- Pak
Platí
T.%1 j = ( m )
2
( i + 2 )
.
Předpokládejme tedy, že Y?j=oJ = 2 a
P°kusme s e
dokázat, že pak také
v^í+l ˇ (i+l)(i+l+l) (í+l)(í+2) -r - i
J2j=o3 =
2 =
2 ˇ '° u z
P'vne
úpravou:
g , = j + ( i + 1 ) = !Íiii+(,+1) =  + ˇ) + *(' + ˇ) = íiiffiií
J=0 j=0
D
etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Důkazy, Indukce
Příklad 2.6. Další indukční důkaz rozepsaný v podrobných krocích.
^n ˇ _ n(n+
-3=0 J -- 2Věta. Pro každé n > O platiJ2TM=0j - ^ 
Důkaz indukcí vzhledem k n.
* Báze: Musíme dokázat tvrzení T(0), což je v tomto případě rovnost
-o ˇ _ 0 ( 0 +
-3=0 J -- 2Yfj=oJ = 2 ˇ "'"ato r o v n o s t
(zjevně) platí.
* Indukční krok: Musíme dokázat následující tvrzení:
Jestliže platí '  5 = 0 j = í o
ř i kde i
> °- Pak
Platí
T.%1 j = ( m )
2
( i + 2 )
.
Předpokládejme tedy, že Y?j=oJ = 2 a
P°kusme s e
dokázat, že pak také
v^í+l ˇ (i+l)(i+l+l) (í+l)(í+2) -r - i
J2j=o3 =
2 =
2 ˇ '° u z
P'vne
úpravou:
ˇ'(i + 1) ,. ^ __ i(i + l) + 2(i + l) (i + l)(i + 2)
 ; = ;+(^i) = -^+(i+i) =2 v
' 2 2
Podle principu matematické indukce je celý důkaz hotov. n
D
etr Hliněný, Fl MU Brno IB000 "Úv. Inf.": Důkazy, Indukce
2.4 Komentáře k matematické indukci
Pro správné a úspěšné použití indukce v dokazování je vhodné si zapamatovat
několik cenných rad:
* Základní trik všech důkazů matematickou indukcí je vhodná reformulace
tvrzení T{n + 1) tak, aby se ,,odvolávalo" na tvrzení T{n).
* Dobře se vždy podívejte, v čem se liší tvrzení T(n +1) od tvrzení T(n).
Tento ,,rozdíl" budete muset v důkaze zdůvodnit.
Petr Hliněný, Fl MU Brno 000 "Úv. Inf.": Důkazy, Indukce
2.4 K o m e n t á ř e k matematické indukci
Pro správné a úspěšné použití indukce v dokazování je vhodné si zapamatovat
několik cenných rad:
* Základní trik všech důkazů matematickou indukcí je vhodná reformulace
tvrzení T{n + 1) tak, aby se ,,odvolávalo" na tvrzení T{n).
* Dobře se vždy podívejte, v čem se liší tvrzení T(n + 1 ) od tvrzení T(n).
Tento ,,rozdíl" budete muset v důkaze zdůvodnit.
* Pozor, občas je potřeba ,,zesílit" tvrzení T{n), aby indukční krok správně
,,fungoval".
Petr Hliněný, Fl MU Brno 10 IB000 "Uv. Inf.": Důkazy, Indukce
2.4 Komentáře k matematické indukci
Pro správné a úspěšné použití indukce v dokazování je vhodné si zapamatovat
několik cenných rad:
* Základní trik všech důkazů matematickou indukcí je vhodná reformulace
tvrzení T{n + 1) tak, aby se ,,odvolávalo" na tvrzení T{n).
* Dobře se vždy podívejte, v čem se liší tvrzení T(n + 1 ) od tvrzení T(n).
Tento ,,rozdíl" budete muset v důkaze zdůvodnit.
* Pozor, občas je potřeba ,,zesílit" tvrzení T{n), aby indukční krok správně
,,fungoval".
* Často se chybuje v důkazu indukčního kroku, neboť ten bývá většinou výrazně
obtížnější než báze,
ale o to zrádnější jsou chyby v samotné zdánlivě snadné bázi!
* Dejte si dobrý pozor, od které hodnoty n > fco je indukční krok univerzálně
platný...
Petr Hliněný, Fl MU Brno 10 IB000 "Uv. Inf.": Důkazy, Indukce
Příklad 2.7. Když je nutno indukční krok zesílit...
Věta. Pro každé n > 1 platí
1
1 1 1
s(n) = 1 1 h ˇ ˇ ˇ + -- r < 1.
w
1-2 2 - 3 3 - 4 n(n + l)
Důkaz:
Petr Hliněný, Fl MU Brno 11 IB000 "Uv. Inf.": Důkazy, Indukce
Příklad 2.7. Když je nutno indukční krok zesílit...
Věta. Pro každé n > 1 platí
1
1 1 1
s(n) = 1 1 h ˇ ˇ ˇ + -- r < 1.
w
1 - 2 2 - 3 3 - 4 n(n + l)
Důkaz: Báze indukce je zřejmá, neboť ^ < 1.
Co však indukční krokl Předpoklad s(n) < 1 je sám o sobě ,,příliš slabý" na to,
aby bylo možno tvrdit s{n + 1) = s(n) + (ra+1)1
(ra+2) < 1Petr
Hliněný, Fl MU Brno 11 IB000 "Uv. Inf.": Důkazy, Indukce
Příklad 2.7. Když je nutno indukční krok zesílit...
Věta. Pro každé n > 1 platí
1
1 1 1
s(n) = 1 1 h ˇ ˇ ˇ + -- r < 1.
w
1 - 2 2 - 3 3 - 4 n(n + l)
Důkaz: Báze indukce je zřejmá, neboť ^ < 1.
Co však indukční krokl Předpoklad s(n) < 1 je sám o sobě ,,příliš slabý" na to,
aby bylo možno tvrdit s{n + 1) = s(n) + (ra+1)1
(ra+2) < 1Neznamená
to ještě, že by tvrzení nebylo platné, jen je potřeba náš indukční
předpoklad zesílit. Budeme dokazovat
,,Pro každé přirozené n > 1 platí s(n) < 1 -- ^ j < 1 . "
Petr Hliněný, Fl MU Brno 11 IB000 "Uv. Inf.": Důkazy, Indukce
Příklad 2.7. Když je nutno indukční krok zesílit...
Věta. Pro každé n > 1 platí
1
1 1 1
s(n) = 1 1 h ˇ ˇ ˇ + -- r < 1.
w
1 - 2 2 - 3 3 - 4 n(n + l)
Důkaz: Báze indukce je zřejmá, neboť y^ < 1.
Co však indukční krokl Předpoklad s(n) < 1 je sám o sobě ,,příliš slabý" na to,
aby bylo možno tvrdit s{n + 1) = s(n) + (ra+1)1
(ra+2) < 1Neznamená
to ještě, že by tvrzení nebylo platné, jen je potřeba náš indukční
předpoklad zesílit. Budeme dokazovat
,,Pro každé přirozené n > 1 platí s(n) < 1 -- ^ j < 1 . "
To platí pro n = 1 a dále už úpravou jen dokončíme zesílený indukční krok:
s(n + l) = s(n) + - -- -- < 1 +
(n + l)(n + 2) ~ n + 1 (n + l)(n + 2)
1 , ~(n + 2) + l = x 1
(n + l)(n + 2) n + 2 D
Petr Hliněný, F 11 IB000 "Úv. Inf.": Důkazy, Indukce
Rozšíření báze a předpokladu
Mimo zesilování tvrzení indukčního kroku jsme někdy okolnostmi nuceni i k
rozšiřování samotné báze indukce a s ní indukčního předpokladu na více než
jednu hodnotu parametru n.
Petr Hliněný, Fl MU Brno 12 IB000 "Uv. Inf.": Důkazy, Indukce
Rozšíření báze a předpokladu
Mimo zesilování tvrzení indukčního kroku jsme někdy okolnostmi nuceni i k
rozšiřování samotné báze indukce a s ní indukčního předpokladu na více než
jednu hodnotu parametru n.
- Můžeme například předpokládat platnost (parametrizovaných) tvrzení T(n)
i T(n + 1) zároveň, a pak odvozovat platnost T(n + 2).
Toto lze samozřejmě zobecnit na jakýkoliv počet předpokládaných parame­
trů.
Petr Hliněný, Fl MU Brno 12 IB000 "Uv. Inf.": Důkazy, Indukce
Rozšíření báze a předpokladu
Mimo zesilování tvrzení indukčního kroku jsme někdy okolnostmi nuceni i k
rozšiřování samotné báze indukce a s ní indukčního předpokladu na více než
jednu hodnotu parametru n.
- Můžeme například předpokládat platnost (parametrizovaných) tvrzení T(n)
i T(n + 1) zároveň, a pak odvozovat platnost T(n + 2).
Toto lze samozřejmě zobecnit na jakýkoliv počet předpokládaných parame­
trů.
- Můžeme dokonce předpokládat platnost tvrzení T(j) pro všechna j =
ko, ko + 1 , . . . , n najednou a dokazovat T(n + 1).
(Toto typicky využijeme v případech, kdy indukční krok ,,rozdělí" problém
T(n + 1) na dvě menší části a z nich pak odvodí platnost T(n + 1).)
Petr Hliněný, Fl MU Brno 12 IB000 "Uv. Inf.": Důkazy, Indukce
Rozšíření báze a předpokladu
Mimo zesilování tvrzení indukčního kroku jsme někdy okolnostmi nuceni i k
rozšiřování samotné báze indukce a s ní indukčního předpokladu na více než
jednu hodnotu parametru n.
- Můžeme například předpokládat platnost (parametrizovaných) tvrzení T(n)
i T(n + 1) zároveň, a pak odvozovat platnost T(n + 2).
Toto lze samozřejmě zobecnit na jakýkoliv počet předpokládaných parame­
trů.
- Můžeme dokonce předpokládat platnost tvrzení T(j) pro všechna j =
ko, ko + 1 , . . . , n najednou a dokazovat T(n + 1).
(Toto typicky využijeme v případech, kdy indukční krok ,,rozdělí" problém
T(n + 1) na dvě menší části a z nich pak odvodí platnost T(n + 1).)
Fakt: Obě prezentovaná ,,rozšíření" jsou v konečném důsledku jen speciálními
instancemi základní matematické indukce; použité rozšířené možnosti pouze
zjednodušují formální zápis důkazu.
Petr Hliněný, Fl MU Brno 12 IB000 "Úv. Inf.": Důkazy, Indukce
Příklad 2.8. Když je nutno rozšířit bázi a indukční předpoklad...
Věta. Nechť funkce f pro každé n > O splňuje vztah f(n + 2) =
2/(n + 1) - f(n). Pokud platí /(O) = 1 a zároveň / ( l ) = 2, tak platí
f(n) = n + 1 pro všechna přirozená n>0.
Petr Hliněný, Fl MU Brno 13 IB000 "Uv. Inf.": Důkazy, Indukce
Příklad 2.8. Když je nutno rozšířit bázi a indukční předpoklad...
Věta. Nechť funkce f pro každé n > O splňuje vztah f(n + 2) =
2/(n + 1) - f(n). Pokud platí /(O) = 1 a zároveň / ( l ) = 2, tak platí
f(n) = n + 1 pro všechna přirozená n>0.
Důkaz: Už samotný pohled na daný vztah f(n + 2) = 2/(n + 1) -- /(n) naznačuje,
že bychom měli rozšířit indukční předpoklad (a krok) zhruba takto:
Pro každé n > 0; jestliže platí Tin); neboli f(n) = n + 1, a zároveň p/ař/'
T(n + 1); f{n + l)=n + 2, pa/c platí také T(n + 2); / ( n + 2) = n + 3.
ßaze indukce Petr
Hliněný, Fl MU Brno 13 IB000 "Uv. Inf.": Důkazy, Indukce
Příklad 2.8. Když je nutno rozšířit bázi a indukční předpoklad...
Věta. Nechť funkce f pro každé n > O splňuje vztah f(n + 2) =
2/(n + 1) - f(n). Pokud platí /(O) = 1 a zároveň / ( l ) = 2, tak platí
f(n) = n + 1 pro všechna přirozená n>0.
Důkaz: Už samotný pohled na daný vztah f(n + 2) = 2/(n + 1) -- /(n) naznačuje,
že bychom měli rozšířit indukční předpoklad (a krok) zhruba takto:
Pro každé n > 0; jestliže platí Tin); neboli f(n) = n + 1, a zároveň p/ař/'
T(n + 1); f{n + l)=n + 2, pa/c platí také T(n + 2); / ( n + 2) = n + 3.
ßaze indukce - pozor, zde už musíme ověřit dvě hodnoty
/(O) = 0 + 1 = 1, /(l) = 1 + 1 = 2.
Petr Hliněný, Fl MU Brno 13 IB000 "Uv. Inf.": Důkazy, Indukce
Příklad 2.8. Když je nutno rozšířit bázi a indukční předpoklad...
Věta. Nechť funkce f pro každé n > O splňuje vztah f(n + 2) =
2/(n + 1) - f(n). Pokud platí /(O) = 1 a zároveň / ( l ) = 2, tak platí
f(n) = n + 1 pro všechna přirozená n>0.
Důkaz: Už samotný pohled na daný vztah f(n + 2) = 2/(n + 1) -- /(n) naznačuje,
že bychom měli rozšířit indukční předpoklad (a krok) zhruba takto:
Pro každé n > 0; jestliže platí Tin); neboli f(n) = n + 1, a zároveň p/ař/'
T(n + 1); f{n + l)=n + 2, pak platí také T{n + 2); /(n + 2) = n + 3.
Báze indukce - pozor, zde už musíme ověřit dvě hodnoty
/(O) = 0 + 1 = 1, /(l) = 1 + 1 = 2.
Náš indukční kroktak nyní může využít celého rozšířeného předpokladu, znalosti
hodnot f(n) i f(n + 1), pro ověření
f(n + 2) = 2f(n + 1) - /(n) = 2-(n + l + l ) - ( n + l ) = n + 3 = n + 2 + l.
D
Jak by tento důkaz měl být formulován v ,,tradiční" indukci?
Petr Hliněný, Fl MU Brno 13 IB000 "Úv. Inf.": Důkazy, Indukce
Příklad 2.8. Když je nutno rozšířit bázi a indukční předpoklad...
Věta. Nechť funkce f pro každé n > O splňuje vztah f(n + 2) =
2/(n + 1) - f(n). Pokud platí /(O) = 1 a zároveň / ( l ) = 2, tak platí
f(n) = n + 1 pro všechna přirozená n>0.
Důkaz: Už samotný pohled na daný vztah f(n + 2) = 2/(n + 1) -- /(n) naznačuje,
že bychom měli rozšířit indukční předpoklad (a krok) zhruba takto:
Pro každé n > 0; jestliže platí Tin); neboli f(n) = n + 1, a zároveň p/ař/'
T(n + 1); f{n + l)=n + 2, pak platí také T{n + 2); /(n + 2) = n + 3.
Báze indukce - pozor, zde už musíme ověřit dvě hodnoty
/(O) = 0 + 1 = 1, /(l) = 1 + 1 = 2.
Náš indukční kroktak nyní může využít celého rozšířeného předpokladu, znalosti
hodnot f(n) i f(n + 1), pro ověření
f(n + 2) = 2f(n + 1) - /(n) = 2-(n + l + l ) - ( n + l ) = n + 3 = n + 2 + l.
D
Jak by tento důkaz měl být formulován v ,,tradiční" indukci? (,,Substitucí".)
Petr Hliněný, Fl MU Brno 13 IB000 "Úv. Inf.": Důkazy, Indukce
Závěrem malý ,,problém"
Příklad 2.9. Aneb jak snadno lze v matematické indukci udělat chybu.
Věta. (,,nevěta")
V každém stádu o n > 1 koních mají všichni koně stejnou barvu.
Petr Hliněný, Fl MU Brno 14 IB000 "Uv. Inf.": Důkazy, Indukce
Závěrem malý ,,problem
Příklad 2.9. Aneb jak snadno lze v matematické indukci udělat chybu.
Věta. (,,nevěta")
V každém stádu o n > 1 koních mají všichni koně stejnou barvu.
Důkaz indukcí vzhledem k n.
Báze: Ve stádu o jednom koni mají všichni koně stejnou barvu.
Petr Hliněný, Fl MU Brno 000 "Úv. Inf.": Důkazy, Indukce
Závěrem malý ,,problem
Příklad 2.9. Aneb jak snadno lze v matematické indukci udělat chybu.
Věta. (,,nevěta")
V každém stádu o n > 1 koních mají všichni koně stejnou barvu.
Důkaz indukcí vzhledem k n.
Báze: Ve stádu o jednom koni mají všichni koně stejnou barvu.
Indukční krok: Nechť S = {K\,..., Kn+\] je stádo o n + 1 koních. Dokážeme,
že všichni koně mají stejnou barvu. Uvažme dvě menší stáda:
- S' = {K,K2,...,Kn}
- S" = {K2,..., Kn, Kn+1}
Petr Hliněný, Fl MU Brno 000 "Úv. Inf.": Důkazy, Indukce
Závěrem malý ,,problem
Příklad 2.9. Aneb jak snadno lze v matematické indukci udělat chybu.
Věta. (,,nevěta")
V každém stádu o n > 1 koních mají všichni koně stejnou barvu.
Důkaz indukcí vzhledem k n.
Báze: Ve stádu o jednom koni mají všichni koně stejnou barvu.
Indukční krok: Nechť S = {K\,..., Kn+\} je stádo o n + 1 koních. Dokážeme,
že všichni koně mají stejnou barvu. Uvažme dvě menší stáda:
- S' = {K,K2,...,Kn}
- S" = {K2,..., Kn, Kn+1}
Podle indukčního předpokladu mají všichni koně ve stádu S' stejnou barvu B'.
Podobně všichni koně ve stádu S" mají podle indukčního předpokladu stejnou
barvu B".
Petr Hliněný, Fl MU Brno 000 "Úv. Inf.": Důkazy, Indukce
Závěrem malý ,,problém"
Příklad 2.9. Aneb jak snadno lze v matematické indukci udělat chybu.
Věta. (,,nevěta")
V každém stádu o n > 1 koních mají všichni koně stejnou barvu.
Důkaz indukcí vzhledem k n.
Báze: Ve stádu o jednom koni mají všichni koně stejnou barvu.
Indukční krok: Nechť S = {K\,..., Kn+\} je stádo o n + 1 koních. Dokážeme,
že všichni koně mají stejnou barvu. Uvažme dvě menší stáda:
- S' = {K,K2,...,Kn}
- S" = {K2,..., Kn, Kn+1}
Podle indukčního předpokladu mají všichni koně ve stádu S' stejnou barvu B'.
Podobně všichni koně ve stádu S" mají podle indukčního předpokladu stejnou
barvu B". Dokážeme, že B' = B", tedy že všichni koně ve stádu S mají stejnou
barvu. To ale plyne z toho, že koně K2,..., Kn patří jak do stáda S', tak i do
stáda S".
Petr Hliněný, Fl MU Brno 14 IB000 "Úv. Inf.": Důkazy, Indukce
Závěrem malý ,,problém"
Příklad 2.9. Aneb jak snadno lze v matematické indukci udělat chybu.
Věta. (,,nevěta")
V každém stádu o n > 1 koních mají všichni koně stejnou barvu.
Důkaz indukcí vzhledem k n.
Báze: Ve stádu o jednom koni mají všichni koně stejnou barvu.
Indukční krok: Nechť S = {K\,..., Kn+\} je stádo o n + 1 koních. Dokážeme,
že všichni koně mají stejnou barvu. Uvažme dvě menší stáda:
- S' = {K,K2,...,Kn}
- S" = {K2,..., Kn, Kn+1}
Podle indukčního předpokladu mají všichni koně ve stádu S' stejnou barvu B'.
Podobně všichni koně ve stádu S" mají podle indukčního předpokladu stejnou
barvu B". Dokážeme, že B' = B", tedy že všichni koně ve stádu S mají stejnou
barvu. To ale plyne z toho, že koně K2,..., Kn patří jak do stáda S', tak i do
stáda S". D
Ale to už je podvod! Vidíte, kde?
Petr Hliněný, Fl MU Brno 14 IB000 "Úv. Inf.": Důkazy, Indukce