Matematická indukce

Tento článek pojednává o metodě matematického důkazu. O způsobu logického uvažování pojednává článek Indukce (logika).

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.

[editovat] 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.

[editovat] Příklad

Mějme následující tvrzení: Pro všechna přirozená $n$ platí

$1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}\,.$

[editovat] Důkaz

[editovat] 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.

[editovat] 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

$1 + 2 + \cdots + m = \frac{m(m + 1)}{2}.$

Přičtením m + 1 k oběma stranám této rovnice dostaneme

$1 + 2 + \cdots + m + (m + 1) = \frac{m(m + 1)}{2} + (m+ 1),$

což se rovná

$= \frac{m(m + 1)}{2} + \frac{2(m + 1)}{2} = \frac{(m + 2)(m + 1)}{2}.$

Máme tedy

$1 + 2 + \cdots + (m + 1) = \frac{(m + 1)((m + 1) + 1)}{2}.$

To je ale přesně tvrzení pro n = m + 1. Dokázali jsme, že je pravdivé, pokud je pravdivé tvrzení pro n = m.

[editovat] 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.

$\vdots$

[editovat] Související články

Související články obsahuje
Portál Matematika

Tento matematický článek je příliš stručný nebo neobsahuje důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte.

Kategorie: Druhy matematických důkazů | Teorie množin

Matematická indukce v jiných jazycích: العربية, Български, বাংলা, Català, Dansk, Deutsch, Ελληνικά, English, Español, فارسی, Suomi, Français, עברית, Magyar, Bahasa Indonesia, Íslenska, Italiano, 日本語, 한국어, Македонски, മലയാളം, Bahasa Melayu, Nederlands, ‪Norsk (nynorsk)‬, ‪Norsk (bokmål)‬, Polski, Português, Română, Русский, Slovenčina, Slovenščina, Српски / Srpski, Svenska, Türkçe, 中文, Bân-lâm-gú

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/Matematick%C3%A1_indukce“
Stránka byla naposledy upravena v Stránka byla naposledy editována 2. 11. 2008 v 15:06.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).