Matematická indukce: Porovnání verzí
m Bot: Nejlepší článek: he:אינדוקציה מתמטית |
m robot přidal: ml:ഗണിതീയ ആഗമനം |
||
Řádek 69: | Řádek 69: | ||
[[Kategorie:Druhy matematických důkazů]] |
[[Kategorie:Druhy matematických důkazů]] |
||
[[Kategorie:Teorie množin]] |
[[Kategorie:Teorie množin]] |
||
{{Link FA|he}} |
|||
[[ar:استقراء رياضي]] |
[[ar:استقراء رياضي]] |
||
Řádek 81: | Řádek 83: | ||
[[fi:Matemaattinen induktio]] |
[[fi:Matemaattinen induktio]] |
||
[[fr:Raisonnement par récurrence]] |
[[fr:Raisonnement par récurrence]] |
||
[[he:אינדוקציה מתמטית]] |
[[he:אינדוקציה מתמטית]] |
||
[[hu:Teljes indukció]] |
[[hu:Teljes indukció]] |
||
[[id:Induksi matematika]] |
[[id:Induksi matematika]] |
||
Řádek 89: | Řádek 91: | ||
[[ko:수학적 귀납법]] |
[[ko:수학적 귀납법]] |
||
[[mk:Индукција]] |
[[mk:Индукција]] |
||
[[ml:ഗണിതീയ ആഗമനം]] |
|||
[[ms:Induksi matematik]] |
[[ms:Induksi matematik]] |
||
[[nl:Inductie (wiskunde)]] |
[[nl:Inductie (wiskunde)]] |
Verze z 20. 8. 2008, 15:12
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 pro číslo 1 platí, 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 n = 1.
- 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. Zřejmě ano, jelikož součet prvních 1 přirozených čísel je 1 a 1(1 + 1)/2=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
což 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 0.
- Jestliže platí pro 0, platí i pro 1.
- Jestliže platí pro 1, platí i pro 2.
- Jestliže platí pro 2, platí i pro 3.