Matematinė indukcija

Matematinė indukcija yra ypatingas matematinės tiesos įrodymo būdas. Juo galima įrodyti, kad kažkas yra teisinga visiems natūraliesiems skaičiams (visiems teigiamiems sveikiesiems skaičiams). Idėja yra ta, kad

Pirmuoju atveju kažkas yra tiesa
Tas pats visada galioja ir kitu atveju

tada

Tas pats pasakytina apie kiekvieną atvejį

Rūpestinga matematikos kalba:

Nurodykite, kad įrodymas bus atliekamas indukcijos būdu per n {\displaystyle n} . ( n {\displaystyle n} yra indukcinis kintamasis.)
Parodykite, kad teiginys teisingas, kai n {\displaystyle n} yra 1.
Tarkime, kad teiginys teisingas bet kuriam natūraliajam skaičiui n {\displaystyle n} . (Tai vadinama indukcijos žingsniu.)

Tada parodykite, kad teiginys teisingas ir kitam skaičiui, n + 1 {\displaystyle n+1} $n+1$ .

Kadangi tai teisinga 1, tai teisinga 1+1 (=2, pagal indukcijos žingsnį), tada teisinga 2+1 (=3), tada teisinga 3+1 (=4) ir t. t.

Indukcinio įrodymo pavyzdys:

Įrodykite, kad visiems natūraliesiems skaičiams n:

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)} $1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)$

Įrodymas:

Pirma, teiginį galima užrašyti taip: visiems natūraliesiems skaičiams n

2 ∑ k = 1 n k = n ( n + 1 ) {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)} $2\sum _{k=1}^{n}k=n(n+1)$

Indukcijos būdu pagal n,

Pirma, jei n=1:

2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} $2\sum _{k=1}^{1}k=2(1)=1(1+1)$ ,

taigi tai tiesa.

Toliau tarkime, kad kai kuriems n=n0 teiginys yra teisingas. Tai yra,:

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)$

Tada, kai n=n0+1:

2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{{n_{0}}+1}k}} $2\sum _{k=1}^{{n_{0}}+1}k$

galima perrašyti

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)} $2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)$

Kadangi 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) , {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),$

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)} $2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)$

Taigi įrodymas yra teisingas.

Panašūs įrodymai

Matematinė indukcija dažnai nurodoma su pradine reikšme 0 (o ne 1). Iš tikrųjų ji taip pat gerai veikia ir su įvairiomis pradinėmis reikšmėmis. Štai pavyzdys, kai pradinė reikšmė yra 3. N {\displaystyle n} kraštinių daugiakampio vidinių kampų suma yra ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ laipsnių.

Pradinė pradinė reikšmė yra 3, o trikampio vidiniai kampai yra ( 3 - 2 ) 180 {\displaystyle (3-2)180} $(3-2)180$ laipsnių. Tarkime, kad n {\displaystyle n} kraštinių daugiakampio vidiniai kampai yra ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ laipsnių. Pridėkite trikampį, kuris figūrą padaro n + 1 {\displaystyle n+1} kampu. $n+1$ kampų skaičius padidėja 180 laipsnių ( n - 2 ) 180 + 180 = ( n + 1 - 2 ) 180 {\displaystyle (n-2)180+180=(n+1-2)180} $(n-2)180+180=(n+1-2)180$ laipsnių. Įrodyta.

Yra labai daug matematinių objektų, kuriems įrodymai matematinės indukcijos būdu yra veiksmingi. Techninis terminas yra gerai sutvarkyta aibė.

Indukcinis apibrėžimas

Ta pati idėja gali būti taikoma ir apibrėžti, ir įrodyti.

Apibrėžkite n {\displaystyle n}-tojo laipsnio pusbrolius:

1 $1$ {\displaystyle 1} 1 {\displaystyle 1} laipsnio pusbrolis yra tėvų brolio ar sesers vaikas.
N + 1 {\displaystyle n+1} $n+1$ pirmojo laipsnio pusbrolis yra tėvų n {\displaystyle n} trečiojo laipsnio pusbrolio vaikas.

Natūraliųjų skaičių aritmetikai taikomas matematine indukcija pagrįstas aksiomų rinkinys. Jis vadinamas Peano aksiomomis. Neapibrėžtieji simboliai yra | ir =.

| yra natūralus skaičius
Jei n {\displaystyle n} yra natūralusis skaičius, tai n | {\displaystyle n|} $n|$ yra natūralusis skaičius
Jei n | = m | {\displaystyle n|=m|} $n|=m|$ , tada n = m {\displaystyle n=m} $n=m$

Tuomet matematinės indukcijos būdu galima apibrėžti sudėties, daugybos ir kt. veiksmus. Pavyzdžiui:

m + | = m | {\displaystyle m+|=m|} $m+|=m|$
m + n | = ( m + n ) | {\displaystyle m+n|=(m+n)|} $m+n|=(m+n)|$

Klausimai ir atsakymai

K: Kas yra matematinė indukcija?

Atsakymas: Matematinė indukcija yra specialus matematinės tiesos įrodymo būdas, kuriuo galima įrodyti, kad nuo tam tikro momento kažkas yra teisinga visiems natūraliesiems skaičiams arba teigiamiesiems skaičiams.

K: Kaip vyksta indukcinis įrodymas?

A: Įrodymas indukcijos būdu paprastai vyksta nurodant, kad įrodymas bus atliekamas per n, parodant, kad teiginys teisingas, kai n yra 1, darant prielaidą, kad teiginys teisingas bet kuriam natūraliajam skaičiui n, ir tada parodant, kad jis teisingas kitam skaičiui (n+1).

Klausimas: Ką reiškia daryti prielaidą indukciniame žingsnyje?

A: Indukciniame žingsnyje ką nors daryti prielaidą reiškia priimti teiginį kaip teisingą, nepateikiant įrodymų ar įrodymų. Tai tarnauja kaip pradinis taškas tolesniam tyrimui.

K: Kokie skaičiai naudojami matematinėje indukcijoje?

A: Matematinėje indukcijoje paprastai naudojami natūralieji arba teigiamieji skaičiai nuo tam tikro momento.

Klausimas: Kaip įrodyti, kad kažkas yra teisinga kitam skaičiui (n+1)?

A: Norėdami įrodyti, kad kažkas yra teisinga kitam skaičiui (n+1), pirmiausia turite įrodyti, kad tai yra teisinga, kai n=1, o tada, naudodamiesi indukcijos žingsnio prielaida, įrodyti, kad tai teisinga ir n+1.