Matematická indukce: Porovnání verzí
Ujasnění proč se, na rozdíl od principu uvedeného v přechozím oddílu, nedokazuje pro n = 0, ale pro n = 1. značka: editace z Vizuálního editoru |
→Indukční krok: úprava pro větší srozumitelnost (místo "což se rovná" specifikováno, že upravujeme pravou stranou). Do výsledku (poslední rovnice) zahrnuto i "m", pro korespondenci s předpokladem značka: editace z Vizuálního editoru |
||
Řádek 29: | Řádek 29: | ||
Nyní chceme ukázat, že pokud tvrzení platí pro ''n'' = ''m'', platí i pro ''n'' = ''m + 1''. Tj. platí-li tvrzení, píšeme-li v něm všude ''m'' místo ''n'', pak platí také píšeme-li v něm všude ''m + 1'' místo ''n''. |
Nyní chceme ukázat, že pokud tvrzení platí pro ''n'' = ''m'', platí i pro ''n'' = ''m + 1''. Tj. platí-li tvrzení, píšeme-li v něm všude ''m'' místo ''n'', pak platí také píšeme-li v něm všude ''m + 1'' místo ''n''. |
||
Předpokládejme tedy, že pro ''n'' = ''m'' tvrzení platí, čili |
Předpokládejme tedy, že pro ''n'' = ''m'' tvrzení platí, čili: |
||
:<math>1 + 2 + \cdots + m = \frac{m(m + 1)}{2}.</math> |
:<math>1 + 2 + \cdots + m = \frac{m(m + 1)}{2}.</math> |
||
Přičtením ''m + 1'' k oběma stranám této rovnice dostaneme |
Přičtením ''m + 1'' k oběma stranám této rovnice dostaneme: |
||
:<math>1 + 2 + \cdots + m + (m + 1) = \frac{m(m + 1)}{2} + (m+ 1),</math> |
:<math>1 + 2 + \cdots + m + (m + 1) = \frac{m(m + 1)}{2} + (m+ 1),</math> |
||
kde pravá strana se rovná: |
|||
:<math> |
:<math> |
||
= \frac{m(m + 1)}{2} + \frac{2(m + 1)}{2} |
= \frac{m(m + 1)}{2} + \frac{2(m + 1)}{2} |
||
= \frac{(m + 1)(m + 2)}{2} |
= \frac{(m + 1)(m + 2)}{2} |
||
= \frac{(m+1)((m+1)+1)}{2}. |
|||
</math> |
</math> |
||
Máme tedy |
Máme tedy: |
||
:<math>1 + 2 + \cdots + (m + 1) = \frac{(m + 1)((m + 1) + 1)}{2}.</math> |
:<math>1 + 2 + \cdots + m + (m + 1) = \frac{(m + 1)((m + 1) + 1)}{2}.</math> |
||
To je ale přesně tvrzení pro ''n'' = ''m + 1''. Dokázali jsme, že je pravdivé, pokud je pravdivé tvrzení pro ''n'' = ''m''. |
To je ale přesně tvrzení pro ''n'' = ''m + 1''. Dokázali jsme, že je pravdivé, pokud je pravdivé tvrzení pro ''n'' = ''m''. |
Verze z 14. 5. 2021, 15:02
Matematická indukce je metoda dokazování matematických vět a tvrzení, která se používá, pokud chceme ukázat, že dané tvrzení platí pro všechna přirozená čísla, případně jinou, předem danou nekonečnou posloupnost. Typicky se užívá k důkazům těch tvrzení o přirozených číslech, u nichž je snadné ověřit, že platí pro číslo 1, a zároveň lze platnost pro každé dané n převést v konečně mnoha krocích na platnost pro 1 s tím, že počet těchto kroků s rostoucím n také roste.
Princip důkazu indukcí
Typický důkaz indukcí se skládá ze dvou kroků:
- První krok: V tomto kroku se dokáže, že tvrzení platí pro nejmenší přirozené číslo n, nikoliv pro n=1, pro které nemusí vždy obecně platit.
- Indukční krok: Ukážeme, že pokud tvrzení platí pro n = m, pak platí i pro n = m + 1 (Část následující bezprostředně po pokud se někdy nazývá indukční předpoklad).
Princip matematické indukce pak již říká, že tvrzení platí pro každé n.
Často se v prvním kroku dokazuje, že tvrzení platí pro n = 0. Tento způsob je zcela ekvivalentní.
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.
Příklad
Mějme následující tvrzení: Pro všechna přirozená platí
Důkaz
První krok
Nejdříve zkontrolujeme, zda tvrzení platí pro n = 1. Je zřejmé že ano, jelikož součet prvních 1 přirozených čísel je 1 a 1(1 + 1)/2=1.
Nedokazujeme pro n = 0, protože v zadání příkladu je uvedeno n ∈ N, tudíž nejmenší n je 1.
Indukční krok
Nyní chceme ukázat, že pokud tvrzení platí pro n = m, platí i pro n = m + 1. Tj. platí-li tvrzení, píšeme-li v něm všude m místo n, pak platí také píšeme-li v něm všude m + 1 místo n.
Předpokládejme tedy, že pro n = m tvrzení platí, čili:
Přičtením m + 1 k oběma stranám této rovnice dostaneme:
kde pravá strana se rovná:
Máme tedy:
To je ale přesně tvrzení pro n = m + 1. Dokázali jsme, že je pravdivé, pokud je pravdivé tvrzení pro n = m.
Shrnutí
Tvrzení tedy platí pro všechna přirozená čísla, jelikož:
- Platí pro 1.
- Jestliže platí pro 1, platí i pro 2.
- Jestliže platí pro 2, platí i pro 3.
- Jestliže platí pro 3, platí i pro 4.
Věta o důkazu indukcí
Myšlenku matematického důkazu indukcí lze formulovat touto matematickou větou:
Buď množina přirozených čísel, která obsahuje nulu a s každým svým prvkem x obsahuje i x+1. Pak .