Matematická indukcia — definícia, princíp a ukážkové dôkazy
Matematická indukcia: jasná definícia, princíp krok‑za‑krokom a názorné ukážkové dôkazy. Naučte sa systematicky dokazovať tvrdenia pre prirodzené čísla.
Matematická indukcia je štandardná technika dokazovania tvrdení, ktoré majú zmysel pre všetky prirodzené čísla. Používa sa vždy, keď chceme ukázať, že nejaké vlastnosti alebo vzťahy platia pre každé prirodzené číslo. Myšlienka je jednoduchá: stačí overiť prvý prípad a potom dokázať, že ak vlastnosť platí pre ľubovoľné n, tak platí aj pre n+1. Potom, opakovaním tohto kroku, dôjdeme k tomu, že platí pre všetky ďalšie čísla.
Základný princíp (krok po kroku)
- Základný prípad (base case): Ukážeme, že tvrdenie platí pre prvé prirodzené číslo (zvyčajne n = 1, niekedy n = 0 alebo iné začiatkové n).
- Indukčný predpoklad (induction hypothesis): Predpokladáme, že tvrdenie platí pre nejaké ľubovoľné, ale pevné n (označme ho n0).
- Indukčný krok (inductive step): Ukážeme, že z platnosti pre n0 plynie platnosť pre n0 + 1.
Ak sú splnené oba kroky, potom tvrdenie platí pre všetky hodnoty n od začiatočného bodu ďalej (pretože z 1 vyplýva 2, z 2 vyplýva 3, atď.).
Varianty a poznámky
- Sílna (úplná) indukcia: Pri tomto variante v indučnom kroku predpokladáme platnosť tvrdenia pre všetky menšie hodnoty (1,2,...,n0) a z toho odvodíme platnosť pre n0+1. Tento variant je ekvivalentný s obyčajnou indukciou, ale často jednoduchší pri dôkazoch, kde n0+1 závisí od viacerých menších hodnôt než len od n0.
- Dôležité: Indukčný krok musí byť dokázaný pre všeobecné n (nie len pre konkrétne n0), t. j. dôkaz má byť platný pre ľubovoľné n0, za ktoré predpoklad platí.
- Začiatočný index: Indukcia môže začínať na inom čísle než 1 (napr. n=0 alebo n=5) podľa toho, kde má tvrdenie zmysel.
Ukážkový dôkaz indukciou — súčet prvých n prirodzených čísel
Ukážeme, že pre všetky prirodzené čísla n platí vzorec
1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)} 
Dôkaz indukciou na n:
Základný prípad: Pre n = 1 máme
2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} 
,
čiže súčet 1 je rovný 1·(1+1)/2 = 1, takže základný prípad platí.
Indukčný predpoklad: Predpokladajme, že pre nejaké n = n0 platí
2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)} 
Indukčný krok: Potrebujeme ukázať, že potom platí aj pre n = n0 + 1. Máme
2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k} 
čo môžeme prepísať ako
2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)} 
Podľa indukčného predpokladu nahradíme 2∑_{k=1}^{n0}k výrazom n0(n0+1):
2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) 
Po vydelení dvoma dostaneme
∑_{k=1}^{n_{0}+1}k={\tfrac{1}{2}}(n_{0}+1)(n_{0}+2)
teda platnosť pre n0+1 je dokázaná. To uzatvára indukčný krok.
Záver: Základný prípad a indukčný krok spolu zabezpečujú, že vzorec platí pre všetky prirodzené čísla n.
Praktické tipy a bežné omyly
- Uistite sa, že základný prípad skutočne začína tam, kde má tvrdenie zmysel (niekedy to nie je n = 1).
- Pri indukčnom kroku formulujte jasne, čo predpokladáte (pre ktoré n) a čo treba dokázať (pre n+1 alebo pre n0+1).
- Nepoužívajte indukčný predpoklad pre n+1 (to by bolo kruhové dokazovanie). Predpoklad sa vzťahuje len na n0, nie na n0+1.
- Silná indukcia je užitočná, keď treba v kroku použiť platnosť pre viacero menších hodnôt než len pre n0.
Matematická indukcia je veľmi všestranný nástroj: používa sa pri dôkazoch vzorcov, nerovností, vlastností deliteľnosti, rekurentných definícií a v mnohých ďalších situáciách. S praxou sa naučíte rozpoznať prípady, kde je indukcia najjednoduchším riešením.
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} 
stupňov.
Počiatočná hodnota je 3 a vnútorné uhly trojuholníka sú ( 3 - 2 ) 180 {\displaystyle (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} stupňov. Pridajte k nemu trojuholník, ktorý z neho urobí n + 1 {\displaystyle 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} 
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}
bratranec a sesternica 1. stupňa je dieťa súrodenca rodiča - Bratranec n + 1 {\displaystyle 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|}
je prirodzené číslo - Ak n | = m | {\displaystyle n|=m|}
potom n = m {\displaystyle n=m} 
Matematickou indukciou potom môžeme definovať operácie sčítania a násobenia atď. Napríklad:
- m + | = m | {\displaystyle m+|=m|}
- m + n | = ( m + n ) | {\displaystyle 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.
Prehľadať