Matematická indukce: Porovnání verzí

Z Wikipedie, otevřené encyklopedie
Smazaný obsah Přidaný obsah
Řádek 30: Řádek 30:
Předpokládejme tedy, že pro ''n'' = ''m'' tvrzení platí, čili
Předpokládejme tedy, že pro ''n'' = ''m'' tvrzení platí, čili


:<math>0 + 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

Verze z 7. 8. 2008, 14:36

Tento článek je 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.

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.

Související články

Šablona:Portál matematika

Šablona:Pahýl - matematika