Silný princip indukce

#veta Silný princip matematické indukce

Nechť a budiž vlastnost celých čísel, která má smysl pro všechna .
Nechť .
Předpokládejme, že následující předpoklady jsou splněny:

  1. Základní krok (ZK): platí.
  2. Indukční krok (IK): Pro každé je pravdivá implikace "Jestliže platí pro všechna , pak platí i ".

Potom dle silného principu matematické indukce (silné indukce) platí pro všechna .

Výrok nazýváme indukční předpoklad.

  • Tam, kde slabý princip nestačí, kde z nemusí plynout , ale je potřeba předpokládat platnost pro více předchozích hodnot,

    • zesílíme IP na

  • Může být potřeba zvýšit hranici pro , od kterého IK používáme

    • zesílíme ZK: ověříme nejen pro nejnižší , ale i pro několik dalších hodnot pro

Příklad

Příklad: "Každé přirozené číslo se dá vyjádřit jako součin prvočísel"
"Pro každé existují prvočísla (ne nutně různá) taková, že "

Důkaz:

  • Základní krok:

    • Pro tvrzení platí. Dvojka je prvočíslo, tedy je i součinem prvočísel.

  • Indukční krok:

    • Pokud tvrzení platí pro , platí pak pro ? (zesílený indukční předpoklad)
    • Je-li prvočíslo, pak ano
    • Je-li složené číslo, pak lze zapsat jako
      • kde a
      • Z indukčního předpokladu lze a vyjádřit jako


        kde všechna jsou prvočísla
      • Tedy a tvrzení platí

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25