Matematická indukcia

Matematická indukcia je špeciálny spôsob dokazovania matematickej pravdy. Možno ju použiť na dokázanie, že niečo je pravdivé pre všetky prirodzené čísla (všetky kladné celé čísla). Ide o to, že

Niečo platí pre prvý prípad
To isté platí vždy aj pre ďalší prípad

potom

To isté platí pre každý prípad

Opatrným jazykom matematiky:

Uveďte, že dôkaz bude indukciou nad n {\displayystyle n} . ( n {\displaystyle n} je indukčná premenná.)
Ukážte, že toto tvrdenie je pravdivé, keď n {\displaystyle n} je 1.
Predpokladajme, že toto tvrdenie je pravdivé pre ľubovoľné prirodzené číslo n {\displayyle n} . (Toto sa nazýva krok indukcie.)

Ukážte, že toto tvrdenie je pravdivé aj pre ďalšie číslo n + 1 {\displayyle n+1} $n+1$ .

Pretože platí pre 1, potom platí pre 1+1 (=2, podľa indukčného kroku), potom platí pre 2+1 (=3), potom platí pre 3+1 (=4) atď.

Príklad dôkazu indukciou:

Dokážte, že pre všetky prirodzené čí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:

Najskôr možno výrok zapísať takto: pre všetky prirodzené čí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)$

Indukciou na n,

Najprv pre 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.

Ďalej predpokladajme, že pre nejaké n=n0 je toto tvrdenie 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)$

Potom pre 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$

možno prepísať

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

Keďž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 teda správny.

Podobné dôkazy

Matematická indukcia sa často uvádza s počiatočnou hodnotou 0 (a nie 1). V skutočnosti bude rovnako dobre fungovať s rôznymi počiatočnými hodnotami. Tu je príklad, keď je počiatočná hodnota 3. Súčet vnútorných uhlov mnohouholníka s n {\displaystyle n} stranami je ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ stupňov.

Počiatočná hodnota je 3 a vnútorné uhly trojuholníka sú ( 3 - 2 ) 180 {\displaystyle (3-2)180} $(3-2)180$ stupňov. Predpokladajme, že vnútorné uhly mnohouholníka s n {\displaystyle n} stranami sú ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ stupňov. Pridajte k nemu trojuholník, ktorý z neho urobí n + 1 {\displaystyle n+1} $n+1$ a tým sa počet uhlov zvýši o 180 stupňov ( 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ňov. Dokázané.

Existuje veľké množstvo matematických objektov, pre ktoré fungujú dôkazy matematickou indukciou. Odborný termín je dobre usporiadaná množina.

Induktívna definícia

Rovnaká myšlienka môže fungovať aj pri definovaní a dokazovaní.

Definujte n {\displaystyle n}tého stupňa bratranca:

1 {\displaystyle 1} $1$ bratranec a sesternica 1. stupňa je dieťa súrodenca rodiča
Bratranec n + 1 {\displaystyle n+1} $n+1$ st. stupňa je potomkom bratranca n {\displaystyle n}.

Existuje súbor axióm pre aritmetiku prirodzených čísel, ktorý je založený na matematickej indukcii. Nazýva sa "Peanove axiómy". Nedefinované symboly sú | a =. Axiómy sú

| je prirodzené číslo
Ak n {\displaystyle n} je prirodzené číslo, potom n | {\displaystyle n|} $n|$ je prirodzené číslo
Ak n | = m | {\displaystyle n|=m|} $n|=m|$ potom n = m {\displaystyle n=m} $n=m$

Matematickou indukciou potom môžeme definovať operácie sčítania a násobenia atď. Napríklad:

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

Otázky a odpovede

Otázka: Čo je matematická indukcia?

Odpoveď: Matematická indukcia je špeciálny spôsob dokazovania matematickej pravdy, ktorý sa dá použiť na dokázanie, že niečo platí pre všetky prirodzené čísla alebo kladné čísla od určitého bodu.

Otázka: Ako prebieha dôkaz indukciou?

Odpoveď: Dôkaz indukciou zvyčajne prebieha tak, že sa uvedie, že dôkaz sa vykoná nad n, ukáže sa, že výrok je pravdivý, keď n je 1, predpokladá sa, že výrok je pravdivý pre každé prirodzené číslo n, a potom sa ukáže, že je pravdivý pre ďalšie číslo (n+1).

Otázka: Čo znamená predpokladať niečo v induktívnom kroku?

Odpoveď: Predpokladať niečo v induktívnom kroku znamená prijať to za pravdivé bez toho, aby sme poskytli dôkaz alebo dôkaz. Slúži to ako východisko pre ďalšie skúmanie.

Otázka: Aké druhy čísel sa používajú v matematickej indukcii?

Odpoveď: Matematická indukcia zvyčajne používa prirodzené čísla alebo kladné čísla od určitého bodu.

Otázka: Ako dokážete, že niečo je pravdivé pre ďalšie číslo (n+1)?

Odpoveď: Ak chcete ukázať, že niečo je pravdivé pre ďalšie číslo (n+1), musíte najprv dokázať, že je to pravdivé, keď n=1, a potom použiť svoj predpoklad z indukčného kroku, aby ste ukázali, že je to pravdivé aj pre n+1.