Matematická indukce: definice, princip a jednoduchý příklad důkazu

Matematická indukce: jasné vysvětlení definice a principu s krok‑za‑krokem jednoduchým příkladem důkazu součtu 1+...+n — srozumitelně i pro začátečníky.

Autor: Leandro Alegsa

Matematická indukce je základní metoda dokazování v matematice, určená zejména pro tvrzení formulovaná pro všechna přirozená čísla. Intuitivně ji lze chápat jako řetězovou reakci: pokud je tvrzení pravdivé pro první případ a z pravdivosti libovolného případu vyplývá pravdivost případu následujícího, pak je pravdivé pro všechny případy. Tuto myšlenku lze formalizovat v několika krocích níže.

Princip

  • Základní krok (base case): prokážeme, že tvrzení platí pro první prvek (např. pro n = 1).
  • Indukční krok (induction step): předpokládáme, že tvrzení platí pro nějaké pevné, ale libovolné n = n0 (tzv. indukční předpoklad) a pak ukážeme, že z tohoto předpokladu plyne, že tvrzení platí i pro n = n0 + 1.
  • Pokud jsou oba kroky splněny, pak tvrzení platí pro všechna přirozená čísla (resp. pro všechna n větší nebo rovna bazickému případu).

Formální jazyk

  • Uveďte, že důkaz bude proveden indukcí nad n {\displayystyle n}
  • Ukažte, že tvrzení je pravdivé, když n je 1 (základní krok).
  • Předpokládejte, že tvrzení je pravdivé pro libovolné přirozené číslo n — tomu se říká indukční předpoklad.
  • Ukažte, že z tohoto předpokladu plyne pravdivost tvrzení i pro {\displaystyle n+1} (indukční krok).

Protože platí pro 1, pak podle indukčního kroku platí i pro 2, poté pro 3, atd. — tedy pro všechna přirozená čísla.

Příklad: součet prvních n přirozených čísel

Dokažme vzorec pro součet prvních n přirozených čísel:

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)} {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)}

Výrok přepíšeme ve tvaru součtu:

∑_{k=1}^{n} k = {\tfrac{1}{2}} n(n+1) — což lze ekvivalentně zapsat i jako

2∑_{k=1}^{n} k = n(n+1) {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)}

Důkaz indukcí na n:

Základní krok (n = 1):

∑_{k=1}^{1} k = 1 = {\tfrac{1}{2}} \cdot 1 \cdot (1+1) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)}

Tvrzení platí pro n = 1.

Indukční krok: Nechť tvrzení platí pro nějaké pevné n = n0, tj. předpokládejme indukční předpoklad

∑_{k=1}^{n_{0}} k = {\tfrac{1}{2}} n_{0}(n_{0}+1) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)}

Musíme ukázat, že pak tvrzení platí i pro n = n0 + 1. Platí

∑_{k=1}^{n_{0}+1} k = \left(\sum_{k=1}^{n_{0}} k\right) + (n_{0}+1). {\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k}

Dosadíme indukční předpoklad:

∑_{k=1}^{n_{0}+1} k = {\tfrac{1}{2}} n_{0}(n_{0}+1) + (n_{0}+1) = (n_{0}+1)\left({\tfrac{1}{2}} n_{0} + 1\right) = {\tfrac{1}{2}}(n_{0}+1)(n_{0}+2). {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)}

Tedy platí

∑_{k=1}^{n_{0}+1} k = {\tfrac{1}{2}}(n_{0}+1)((n_{0}+1)+1), {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)}

tedy vzorec platí i pro n = n0 + 1. Indukční krok je dokončen a důkaz je správný.

Alternativní vysvětlení (párování)

Pro ilustraci lze součet 1 + 2 + ... + n také odvodit párováním členů: když sečteme první a poslední člen, druhý a předposlední atd., vznikne n/2 párů (pro sudé n) každého součtu n+1, takže součet je (n/2)(n+1). Pro liché n zůstane uprostřed prostřední člen (n+1)/2 a celkový výsledek je stejný: n(n+1)/2.

Poznámky a časté chyby

  • Indukce neznamená pouze opakování mechanického postupu; klíčová je správná formulace indukčního předpokladu a přesné odvození kroku n0 → n0+1.
  • Je-li základní případ jiné než n = 1 (např. n = 0 nebo n = 5), je třeba ho explicitně uvést a indukci provádět od něj dál. Indukce garantuje pravdivost pouze od zvoleného bazického případu výše.
  • Existuje i silná (úplná) indukce, kde v indukčním kroku předpokládáme pravdivost tvrzení pro všechna menší čísla než n0 a z toho odvozujeme pravdivost pro n0; tato varianta je užitečná například při důkazech o prvočíselných faktorizacích nebo rekurentních vazbách.

Matematická indukce je velmi užitečný nástroj — po osvojení si principu a častých triků (volba správného indukčního předpokladu, úprava algebraických výrazů) se stává přirozenou součástí pracovního arzenálu při formálním dokazování.

Podobné důkazy

Matematická indukce se často uvádí s počáteční hodnotou 0 (nikoli 1). Ve skutečnosti však funguje stejně dobře s různými počátečními hodnotami. Zde je příklad, kdy je počáteční hodnota 3. Součet vnitřních úhlů mnohoúhelníku o n {\displaystyle n}n stranách je ( n - 2 ) 180 {\displaystyle (n-2)180} {\displaystyle (n-2)180}stupňů.

Počáteční výchozí hodnota je 3 a vnitřní úhly trojúhelníku jsou ( 3 - 2 ) 180 {\displaystyle (3-2)180} {\displaystyle (3-2)180}stupňů. Předpokládejte, že vnitřní úhly mnohoúhelníku o n {\displaystyle n}n stranách jsou ( n - 2 ) 180 {\displaystyle (n-2)180} {\displaystyle (n-2)180}stupňů. Přidejte k němu trojúhelník, který z něj vytvoří n + 1 {\displaystyle n+1} úhelníků. {\displaystyle n+1}tím se počet úhlů zvýší o 180 stupňů ( n - 2 ) 180 + 180 = ( n + 1 - 2 ) 180 {\displaystyle (n-2)180+180=(n+1-2)180} {\displaystyle (n-2)180+180=(n+1-2)180}stupňů. Dokázáno.

Existuje velké množství matematických objektů, pro které funguje důkaz matematickou indukcí. Odborný termín je dobře uspořádaná množina.

Induktivní definice

Stejná myšlenka může fungovat jak při definování, tak při dokazování.

Definujte n {\displaystyle n}n bratranců třetího stupně:

  • 1 {\displaystyle 1}{\displaystyle 1} bratranec a sestřenice st. stupně je potomkem sourozence rodiče.
  • Bratranec n + 1 {\displaystyle n+1}{\displaystyle n+1} st. stupně je potomkem bratrance n {\displaystyle n}n. stupně rodiče.

Pro aritmetiku přirozených čísel existuje soubor axiomů, který je založen na matematické indukci. Nazývá se "Peanovy axiomy". Nedefinované symboly jsou | a =. Axiomy jsou následující

  • | je přirozené číslo
  • Je-li n {\displaystyle n}n přirozené číslo, pak n | {\displaystyle n|}{\displaystyle n|} je přirozené číslo
  • Pokud n | = m | {\displaystyle n|=m|}{\displaystyle n|=m|} pak n = m {\displaystyle n=m} {\displaystyle n=m}

Matematickou indukcí pak lze definovat operace sčítání a násobení atd. Například:

  • m + | = m | {\displaystyle m+|=m|} {\displaystyle m+|=m|}
  • m + n | = ( m + n ) | {\displaystyle m+n|=(m+n)|} {\displaystyle m+n|=(m+n)|}

Otázky a odpovědi

Otázka: Co je to matematická indukce?


Odpověď: Matematická indukce je speciální způsob důkazu matematické pravdy, který lze použít k důkazu, že něco platí pro všechna přirozená čísla nebo kladná čísla od určitého bodu.

Otázka: Jak probíhá důkaz indukcí?


Odpověď: Důkaz indukcí obvykle probíhá tak, že se uvede, že důkaz bude proveden nad n, ukáže se, že tvrzení je pravdivé, když n je 1, předpokládá se, že tvrzení je pravdivé pro každé přirozené číslo n, a pak se ukáže, že je pravdivé pro další číslo (n+1).

Otázka: Co znamená předpokládat něco v induktivním kroku?


Odpověď: Předpokládat něco v induktivním kroku znamená přijmout to jako pravdivé, aniž bychom předložili důkaz nebo potvrzení. Slouží jako výchozí bod pro další zkoumání.

Otázka: Jaké druhy čísel se používají v matematické indukci?


Odpověď: Matematická indukce obvykle používá přirozená čísla nebo od určitého okamžiku kladná čísla.

Otázka: Jak dokážete, že něco platí pro další číslo (n+1)?


Odpověď: Chcete-li dokázat, že něco platí pro další číslo (n+1), musíte nejprve dokázat, že to platí, když n=1, a pak použít svůj předpoklad z indukčního kroku, abyste dokázali, že to platí i pro n+1.


Vyhledávání
AlegsaOnline.com - 2020 / 2025 - License CC3