Matematisk induktion

Matematisk induktion är en metod för matematiska bevis som används för att bevisa sanningen i något påstående för alla naturliga tal . För att göra detta kontrolleras först sanningen av påståendet med numret - basen (basen) för induktionen, och sedan bevisas det att om påståendet med numret är sant, så är nästa påstående med numret också sant - induktionssteget, eller induktionsövergången. $ett$ $n$ $n+1$

Beviset genom induktion kan representeras visuellt i form av den så kallade dominoprincipen . Låt valfritt antal dominobrickor ordnas i rad på ett sådant sätt att varje domino, som faller, nödvändigtvis välter nästa domino (detta är den induktiva övergången). Sedan, om vi trycker på det första benet (detta är basen för induktion), kommer alla ben i raden att falla.

Formulering

Antag att det krävs för att fastställa giltigheten av en oändlig sekvens av påståenden, numrerade med naturliga tal : . $P_{1},P_{2},\ldots ,P_{n},P_{{n+1}},\ldots$

Låt oss anta det

Fanns vara sant. (Detta uttalande kallas grunden för induktion .) $P_1$
För alla är det bevisat att om det är sant , så är det sant . (Detta uttalande kallas det induktiva steget .) $n$ $P_{n}$ $P_{{n+1}}$

Då är alla påståenden i vår sekvens sanna.

Den logiska grunden för denna bevismetod är det så kallade induktionsaxiomet , det femte av Peanos axiom som definierar de naturliga talen . Riktigheten av induktionsmetoden är likvärdig med det faktum att det i varje icke-tom delmängd av naturliga tal finns ett minimielement.

Principen för fullständig matematisk induktion

Det finns också en variant, den så kallade principen om fullständig matematisk induktion. Här är dess strikta formulering:

Låt det finnas en sekvens av uttalanden , , , . Om för något naturligt av det faktum att alla , , , , är sanna , följer det också att , då är alla påståenden i denna sekvens sanna, det vill säga . $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 )}\Högerpil (\forall n\in {\mathbb {N} })P_{n))$

I denna variant visar sig induktionsbasen vara redundant, eftersom det är ett trivialt specialfall av den induktiva övergången. Ja, om villkoret är exakt likvärdigt (det finns inget att följa av dess sanning). Men man måste fortfarande ofta bevisa det induktiva steget för separat, så det är rimligt att peka ut denna del av det som bas. $n=1$ ${\displaystyle (\forall i\in \{1;\dots ;n-1\})P_{i}\Rightarrow P_{n))$ $P_1$ $P_1$

Principen för fullständig matematisk induktion är likvärdig med induktionens axiom i Peanos axiom .

Det är också en direkt tillämpning av den starkare transfinita induktionen .

Historik

Medvetenhet om metoden för matematisk induktion som en separat viktig metod går tillbaka till Blaise Pascal och Gersonides , även om vissa fall av tillämpning finns i antiken av Proclus och Euclid [1] . Det moderna namnet på metoden introducerades av de Morgan 1838 .

Exempel

Summan av en geometrisk progression. Bevisa att jämlikheten gäller , oavsett vad det är naturligt och verkligt $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}}.

Bevis. Genom induktion på för en godtycklig . $n$ $q$

Låt oss bevisa induktionsbasen för : $n=1$

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

Låt oss bevisa övergången : anta att för $n=k$

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

sedan för , enligt antagandet: $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}}

Därför, genom principen om matematisk induktion, gäller jämlikheten för alla . Q.E.D. $n$

Kommentar: sanningen i påståendet i detta bevis är detsamma som sanningen om jämlikheten $P_{n}$

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

Viktiga exempel: Bernoullis ojämlikhet , Newtons binomial .

Variationer och generaliseringar

Se även

Matematisk sofism#Bevis genom induktion
- Bevis på att alla hästar är monokromatiska

Anteckningar

↑ Nachum L. Rabinovih. Rabbi Levi ben Gershom och ursprunget till matematisk induktion // Archive for History of Exact Sciences . - 1970. - Utgåva. 6 . - S. 237-248 .

Litteratur

A. Shen. Matematisk induktion . - MTsNMO , 2004. - 36 sid.
N. Ya. Vilenkin . Induktion. Kombinatorik. – En guide för lärare. - M . : Utbildning, 1976. - 48 sid.
L. I. Golovina, I. M. Yaglom . Induktion i geometri . - Fizmatgiz , 1961. - T. 21. - 100 sid. - ( Populära föreläsningar om matematik ).
R. Courant , G. Robbins. Kapitel I, § 2 // Vad är matematik?
I. S. Sominsky. Metoden för matematisk induktion . - Nauka, 1965. - T. 3. - 58 sid. - ( Populära föreläsningar om matematik ).

Länkar

Video om metoden för matematisk induktion

Ordböcker och uppslagsverk	Stor ryss Kroatisk Britannica (online) Moderna Ukraina
I bibliografiska kataloger	GND : 4124408-4 J9U : 987007548367405171 LCCN : sh85065806