Matematická indukce

Matematická indukce je metoda matematického důkazu , která se používá k prokázání pravdivosti nějakého tvrzení pro všechna přirozená čísla . K tomu se nejprve zkontroluje pravdivost výroku s číslem - základ (základ) indukce a následně se prokáže, že pokud je pravdivý výrok s číslem , pak je i další výrok s číslem true - indukční krok nebo indukční přechod. $jeden$ $n$ $n+1$

Důkaz indukcí lze vizuálně znázornit formou tzv. dominového principu . Nechť je libovolný počet kostek domina uspořádán za sebou tak, aby každé padající domino nutně převrátilo další domino (to je indukční přechod). Pak, když zatlačíme na první kost (to je základ indukce), pak všechny kosti v řadě spadnou.

Formulace

Předpokládejme, že je požadováno stanovení platnosti nekonečné posloupnosti výroků číslovaných přirozenými čísly : . $P_{1},P_{2},\ldots ,P_{n},P_{{n+1}},\ldots$

Předpokládejme to

Bylo zjištěno, že je to pravda. (Toto tvrzení se nazývá základ indukce .) $P_1$
Pro všechny je dokázáno, že když je to pravda , pak je to pravda . (Toto tvrzení se nazývá indukční krok .) $n$ $P_{n}$ $P_{{n+1}}$

Pak jsou všechna tvrzení v naší posloupnosti pravdivá.

Logickým základem pro tuto metodu důkazu je takzvaný axiom indukce , pátý z Peanových axiomů , které definují přirozená čísla . Správnost metody indukce je ekvivalentní tomu, že v každé neprázdné podmnožině přirozených čísel je minimální prvek.

Princip úplné matematické indukce

Existuje také obměna, tzv. princip úplné matematické indukce. Zde je jeho striktní znění:

Nechť existuje posloupnost příkazů , , , . Jestliže pro nějaké přirozené z toho, že všechny , , , , jsou pravdivé , z toho také vyplývá, že , pak jsou pravdivé všechny výroky v této posloupnosti, tedy . $P_1$ $P_2$ $P_{3}$ $\ldots$ $n$ $P_1$ $P_2$ $P_{3}$ $\ldots$ $P_{{n-1}}$ $P_{n}$ ${\displaystyle (\forall n\in {\mathbb {N} }){\Big (}(\forall i\in \{1;\tečky ;n-1\})P_{i}\Rightarrow P_{n }{\Big )}\Rightarrow (\forall n\in {\mathbb {N} })P_{n))$

V této variantě se indukční báze ukazuje jako nadbytečná, protože jde o triviální speciální případ indukčního přechodu. Pokud je totiž podmínka přesně ekvivalentní (z její pravdy nic nevyplývá). Indukční krok se však stále musí často dokazovat samostatně, takže je rozumné vyčlenit tuto jeho část jako základ. $n=1$ ${\displaystyle (\forall i\in \{1;\tečky ;n-1\})P_{i}\Rightarrow P_{n))$ $P_1$ $P_1$

Princip úplné matematické indukce je ekvivalentní axiomu indukce v Peanových axiomech .

Je to také přímá aplikace silnější transfinitní indukce .

Historie

Povědomí o metodě matematické indukce jako samostatné důležité metodě sahá až k Blaise Pascalovi a Gersonidesovi , i když některé případy aplikace nalezli ve starověku Proclus a Euclid [1] . Moderní název pro metodu zavedl de Morgan v roce 1838 .

Příklady

Součet geometrické posloupnosti. Dokažte, že bez ohledu na to, co je přirozené a skutečné , platí rovnost $n$ $q\neq 1$

\sum _{i=0}^{n}q^{i}\equiv 1+q+q^{2}+\cdots +q^{n}={\frac {1-q^{ n+1}}{1-q}}.

Důkaz. Indukcí na libovolnou . $n$ $q$

Dokažme indukční základnu pro : $n=1$

1+q={\frac {(1-q)(1+q)}{1-q}}={\frac {1-q^{{1+1}}}{1-q}}.

Pojďme dokázat přechod : předpokládejme, že pro $n=k$

1+q+\cdots +q^{k}={\frac {1-q^{k+1}}{1-q)),

pak pro , podle předpokladu: $n=k+1$

1+q+\cdots +q^{k}+q^{k+1}={\frac {1-q^{k+1}}{1-q}}+q^{k+1 }=

={\frac {1-q^{k+1}+(1-q)q^{k+1}}{1-q}}={\frac {1-q^{k+1 }+q^{k+1}-q^{(k+1)+1}}{1-q}}={\frac {1-q^{(k+1)+1}}{1- q}}

Z principu matematické indukce tedy platí rovnost pro všechny . Q.E.D. $n$

Komentář: pravdivost tvrzení v tomto důkazu je stejná jako pravdivost rovnosti $P_{n}$

1+q+\cdots +q^{n}={\frac {1-q^{{n+1}}}{1-q}}.

Důležité příklady: Bernoulliho nerovnost , Newtonův binom .

Variace a zobecnění

Viz také

Matematický sofismus#Důkaz indukcí
- Důkaz, že všichni koně jsou jednobarevní

Poznámky

↑ Nachum L. Rabinovih. Rabbi Levi ben Gershom a počátky matematické indukce // Archiv pro historii exaktních věd . - 1970. - Vydání. 6 . - S. 237-248 .

Literatura

A. Shen. Matematická indukce . - MTsNMO , 2004. - 36 s.
N. Ya Vilenkin . Indukce. Kombinatorika. - Průvodce pro učitele. - M . : Vzdělávání, 1976. - 48 s.
L. I. Golovina, I. M. Yaglom . Indukce v geometrii . - Fizmatgiz , 1961. - T. 21. - 100 s. - ( Populární přednášky o matematice ).
R. Courant , G. Robbins. Kapitola I, § 2 // Co je matematika?
I. S. Sominskij. Metoda matematické indukce . - Nauka, 1965. - T. 3. - 58 s. - ( Populární přednášky o matematice ).

Odkazy

Video o metodě matematické indukce

Slovníky a encyklopedie	Velký Rus chorvatský Britannica (online) Moderní Ukrajina
V bibliografických katalozích	GND : 4124408-4 J9U : 987007548367405171 LCCN : sh85065806