Matematisk induktion

Matematisk induktion er en metode til matematisk bevis , der bruges til at bevise sandheden af et udsagn for alle naturlige tal . For at gøre dette kontrolleres først sandheden af udsagnet med tallet - grundlaget (grundlaget) for induktionen, og derefter bevises det, at hvis udsagnet med tallet er sandt, så er den næste sætning med tallet også sand - induktionstrinnet eller induktionsovergangen. $en$ $n$ $n+1$

Beviset ved induktion kan visuelt repræsenteres i form af det såkaldte dominoprincip . Lad et hvilket som helst antal dominobrikker arrangeres i en række på en sådan måde, at hver domino, der falder, nødvendigvis vælter den næste domino (dette er den induktive overgang). Så, hvis vi skubber den første knogle (dette er bunden af induktion), så vil alle knoglerne i rækken falde.

Ordlyd

Antag, at det er nødvendigt at fastslå gyldigheden af en uendelig række af udsagn, nummereret med naturlige tal : . $P_{1},P_{2},\ldots ,P_{n},P_{{n+1}},\ldots$

Lad os antage det

Fundet at være sandt. (Dette udsagn kaldes induktionsgrundlaget .) $P_1$
For enhver er det bevist, at hvis er sandt , så er det sandt . (Denne erklæring kaldes det induktive trin .) $n$ $P_{n}$ $P_{{n+1}}$

Så er alle udsagn i vores rækkefølge sande.

Det logiske grundlag for denne bevismetode er det såkaldte induktionsaksiom , det femte af Peanos aksiomer , der definerer de naturlige tal . Rigtigheden af induktionsmetoden svarer til det faktum, at der i enhver ikke-tom delmængde af naturlige tal er et minimumselement.

Princippet om fuldstændig matematisk induktion

Der er også en variation, det såkaldte princip om fuldstændig matematisk induktion. Her er dens strenge formulering:

Lad der være en række udsagn , , , . Hvis for nogen naturlig fra det faktum, at alle , , , , er sande , følger det også at , så er alle udsagn i denne rækkefølge sande, dvs. $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øjrepil (\forall n\in {\mathbb {N} })P_{n))$

I denne variation viser induktionsbasen sig at være overflødig, da det er et trivielt specialtilfælde af den induktive overgang. Faktisk, hvis betingelsen er nøjagtigt ækvivalent (der er intet at følge af dens sandhed). Men man skal stadig ofte bevise det induktive trin for separat, så det er rimeligt at udskille denne del af det som en base. $n=1$ ${\displaystyle (\forall i\in \{1;\dots ;n-1\})P_{i}\Rightarrow P_{n))$ $P_1$ $P_1$

Princippet om fuldstændig matematisk induktion svarer til induktionsaksiomet i Peanos aksiomer .

Det er også en direkte anvendelse af den stærkere transfinite induktion .

Historie

Bevidstheden om metoden til matematisk induktion som en separat vigtig metode går tilbage til Blaise Pascal og Gersonides , selvom nogle tilfælde af anvendelse er fundet i oldtiden af Proclus og Euclid [1] . Det moderne navn for metoden blev introduceret af de Morgan i 1838 .

Eksempler

Summen af en geometrisk progression. Bevis, at uanset hvad det naturlige og virkelige er, gælder ligheden $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. Ved induktion på for en vilkårlig . $n$ $q$

Lad os bevise induktionsgrundlaget for : $n=1$

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

Lad os bevise overgangen : antag, at for $n=k$

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

derefter for , ifølge antagelsen: $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}}

Derfor, ved princippet om matematisk induktion, gælder ligheden for enhver . Q.E.D. $n$

Kommentar: sandheden af udsagnet i dette bevis er den samme som sandheden om ligheden $P_{n}$

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

Vigtige eksempler: Bernoullis ulighed , Newtons binomiale .

Variationer og generaliseringer

Se også

Matematisk sofisme#Bevis ved induktion
- Bevis på at alle heste er monokromatiske

Noter

↑ Nachum L. Rabinovih. Rabbi Levi ben Gershom og oprindelsen af matematisk induktion // Arkiv for nøjagtige videnskabers historie . - 1970. - Udgave. 6 . - S. 237-248 .

Litteratur

A. Shen. Matematisk induktion . - MTsNMO , 2004. - 36 s.
N. Ya. Vilenkin . Induktion. Kombinatorik. - En vejledning til lærere. - M . : Uddannelse, 1976. - 48 s.
L. I. Golovina, I. M. Yaglom . Induktion i geometri . - Fizmatgiz , 1961. - T. 21. - 100 s. - ( Populære foredrag om matematik ).
R. Courant , G. Robbins. Kapitel I, § 2 // Hvad er matematik?
I. S. Sominsky. Metoden til matematisk induktion . - Nauka, 1965. - T. 3. - 58 s. - ( Populære foredrag om matematik ).

Links

Video om metoden til matematisk induktion

Ordbøger og encyklopædier	Stor russer kroatisk Britannica (online) Moderne Ukraine
I bibliografiske kataloger	GND : 4124408-4 J9U : 987007548367405171 LCCN : sh85065806