Matemaattinen induktio

Matemaattinen induktio on matemaattisen todistuksen menetelmä, jota käytetään todistamaan jonkin väitteen totuus kaikille luonnollisille luvuille . Tätä varten tarkistetaan ensin lauseen totuus numerolla - induktion kanta (perusta) ja sitten todistetaan, että jos lauseke numerolla on totta, niin seuraava lauseke numerolla on myös true - induktiovaihe tai induktiosiirtymä. $yksi$ $n$ $n+1$

Induktiotodistus voidaan esittää visuaalisesti ns. dominoperiaatteen muodossa . Järjestetään mikä tahansa määrä dominoa peräkkäin siten, että jokainen putoava domino väistämättä kaataa seuraavan dominon (tämä on induktiivinen siirtymä). Sitten, jos työnnämme ensimmäistä luuta (tämä on induktion perusta), kaikki rivin luut putoavat.

Sanamuoto

Oletetaan, että vaaditaan luonnollisilla luvuilla numeroitujen lauseiden äärettömän sarjan pätevyys : . $P_{1},P_{2},\ldots ,P_{n},P_{{n+1}},\ldots$

Oletetaan, että

Todettu olevan totta. (Tätä lausetta kutsutaan induktion perustaksi .) $P_1$
Jokaiselle on todistettu, että jos on totta , niin se on totta . (Tätä lausetta kutsutaan induktiiviseksi askeleeksi .) $n$ $P_{n}$ $P_{{n+1}}$

Silloin kaikki sekvenssimme väitteet ovat tosia.

Tämän todistusmenetelmän looginen perusta on ns . induktioaksiooma , viides Peanon aksioomista , joka määrittelee luonnolliset luvut . Induktiomenetelmän oikeellisuus vastaa sitä tosiasiaa, että missä tahansa luonnollisten lukujen ei-tyhjässä osajoukossa on minimialkio.

Täydellisen matemaattisen induktion periaate

On myös muunnelma, niin kutsuttu täydellisen matemaattisen induktion periaate. Tässä sen tiukka sanamuoto:

Olkoon lausesarja , , , . Jos jollekin luonnolliselle siitä, että kaikki , , , , ovat tosia , seuraa myös, että , niin kaikki tämän sekvenssin lausumat ovat tosia, eli . $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;\dots ;n-1\})P_{i}\Rightarrow P_{n }{\Big )}\Rightarrow (\forall n\in {\mathbb {N} })P_{n))$

Tässä muunnelmassa induktiokanta osoittautuu redundantiksi, koska se on triviaali induktiivisen siirtymän erikoistapaus. Todellakin, jos ehto on täsmälleen sama (sen totuudesta ei voi seurata mitään). Usein kuitenkin joutuu todistamaan induktiivisen askeleen erikseen, joten tämä osa siitä on järkevää nostaa pohjaksi. $n = 1$ ${\displaystyle (\forall i\in \{1;\dots ;n-1\})P_{i}\Rightarrow P_{n))$ $P_1$ $P_1$

Täydellisen matemaattisen induktion periaate vastaa Peanon aksioomien induktion aksioomia .

Se on myös voimakkaamman transfiniittisen induktion suora sovellus .

Historia

Tietoisuus matemaattisen induktion menetelmästä erillisenä tärkeänä menetelmänä juontaa juurensa Blaise Pascaliin ja Gersonidesiin , vaikka Proclus ja Euclid ovat löytäneet joitakin käyttötapauksia muinaisina aikoina [1] . De Morgan esitteli menetelmän nykyaikaisen nimen vuonna 1838 .

Esimerkkejä

Geometrisen progression summa. Todista, että mikä tahansa luonnollinen ja todellinen , tasa-arvo pätee $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}}.

Todiste. Induktiolla päälle mielivaltaiselle . $n$ $q$

Todistetaan induktiokanta : _ $n = 1$

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

Todistetaan siirtymä : oletetaan, että varten $n=k$

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

sitten , oletuksen mukaan: $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}}

Näin ollen matemaattisen induktion periaatteen mukaan yhtäläisyys pätee mille tahansa . Q.E.D. $n$

Kommentti: tämän todistuksen väitteen totuus on sama kuin tasa-arvon totuus $P_{n}$

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

Tärkeitä esimerkkejä: Bernoullin epäyhtälö , Newtonin binomi .

Muunnelmia ja yleistyksiä

Katso myös

Matemaattinen sofismi#Todistaminen induktiolla
- Todiste siitä, että kaikki hevoset ovat yksivärisiä

Muistiinpanot

↑ Nachum L. Rabinovih. Rabbi Levi ben Gershom ja matemaattisen induktion alkuperä // Tarkkojen tieteiden historian arkisto . - 1970. - Numero. 6 . - S. 237-248 .

Kirjallisuus

A. Shen. Matemaattinen induktio . - MTsNMO , 2004. - 36 s.
N. Ya. Vilenkin . Induktio. Kombinatoriikka. - Opas opettajille. - M . : Koulutus, 1976. - 48 s.
L. I. Golovina, I. M. Yaglom . Induktio geometriassa . - Fizmatgiz , 1961. - T. 21. - 100 s. - ( Suosittuja matematiikan luentoja ).
R. Courant , G. Robbins. Luku I, § 2 // Mitä on matematiikka?
I.S. Sominsky. Matemaattisen induktion menetelmä . - Nauka, 1965. - T. 3. - 58 s. - ( Suosittuja matematiikan luentoja ).

Linkit

Video matemaattisen induktion menetelmästä

Sanakirjat ja tietosanakirjat	Iso venäläinen kroatialainen Britannica (verkossa) Moderni Ukraina
Bibliografisissa luetteloissa	GND : 4124408-4 J9U : 987007548367405171 LCCN : sh85065806