Matematická indukce

Matematická indukce je zvláštní způsob důkazu matematické pravdy. Lze ji použít k důkazu, že něco platí pro všechna přirozená čísla (všechna celá kladná čísla). Myšlenka spočívá v tom, že

Něco platí pro první případ
Totéž platí vždy pro další případ.

pak

To samé platí pro všechny případy

Opatrným jazykem matematiky:

Uveďte, že důkaz bude proveden indukcí nad n {\displayystyle n} . ( n {\displaystyle n} je indukční proměnná.)
Ukažte, že toto tvrzení je pravdivé, když n {\displaystyle n} je 1.
Předpokládejte, že toto tvrzení je pravdivé pro libovolné přirozené číslo n {\displayyle n} . (Tomu se říká krok indukce.)

Ukažte, že toto tvrzení platí i pro další číslo, n + 1 {\displayyle n+1} $n+1$ .

Protože platí pro 1, pak platí pro 1+1 (=2, podle kroku indukce), pak platí pro 2+1 (=3), pak platí pro 3+1 (=4) atd.

Příklad důkazu indukcí:

Dokažte, že pro všechna přirozená čísla n:

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

Důkaz:

Nejprve lze zapsat větu: pro všechna přirozená čísla n

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

Indukcí na n,

Nejprve pro n=1:

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

takže je to pravda.

Dále předpokládejme, že pro nějaké n=n0 je tvrzení pravdivé. To znamená, že:

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

Pak pro n=n0+1:

2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k} $2\sum _{k=1}^{{n_{0}}+1}k$

lze přepsat

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

Protože 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) , {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),$

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

Důkaz je tedy správný.

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} stranách je ( n - 2 ) 180 {\displaystyle (n-2)180} $(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} $(3-2)180$ stupňů. Předpokládejte, že vnitřní úhly mnohoúhelníku o n {\displaystyle n} stranách jsou ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ stupňů. Přidejte k němu trojúhelník, který z něj vytvoří n + 1 {\displaystyle n+1} úhelníků. $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} $(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} bratranců třetího stupně:

1 {\displaystyle 1} $1$ bratranec a sestřenice st. stupně je potomkem sourozence rodiče.
Bratranec n + 1 {\displaystyle n+1} $n+1$ st. stupně je potomkem bratrance n {\displaystyle 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} přirozené číslo, pak n | {\displaystyle n|} $n|$ je přirozené číslo
Pokud n | = m | {\displaystyle n|=m|} $n|=m|$ pak n = m {\displaystyle n=m} $n=m$

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

m + | = m | {\displaystyle m+|=m|} $m+|=m|$
m + n | = ( m + n ) | {\displaystyle m+n|=(m+n)|} $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.