Matematická indukce

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á $n$ platí

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

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:

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),

kde pravá strana se rovná:

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

Máme tedy:

1 2 \cdots  m (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.

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$

Věta o důkazu indukcí

Myšlenku matematického důkazu indukcí lze formulovat touto matematickou větou:

Buď $A\subset \mathbb {N} ^{0}\,\!$ množina přirozených čísel, která obsahuje nulu a s každým svým prvkem x obsahuje i x 1. Pak $A=\mathbb {N} ^{0}\,\!$ .

Související články

Externí odkazy

Obrázky, zvuky či videa k tématu Matematická indukce na Wikimedia Commons

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.