Matematinė indukcija: apibrėžimas, įrodymo žingsniai ir pavyzdžiai

Matematinė indukcija yra vienas iš pagrindinių būdų įrodyti teiginius, kurie teisingi visiems natūraliesiems skaičiams. Paprastai ji taikoma, kai reikia parodyti, kad tam tikra savybė galioja visiems teigiamiesiems sveikiesiems skaičiams. Idėja labai paprasta: jei galime įrodyti, kad savybė galioja pirmajam skaičiui, ir parodome, kad iš jos teisingumo bet kuriam skaičiui seka teisingumas kitam (dažniausiai n+1), tai ši savybė galioja visiems skaičiams.

Idėja trumpai

• Įrodome, jog teiginys galioja pradiniam skaičiui (dažniausiai n = 1).
• Parodome, kad jei teiginys galioja už tam tikrą n, tai jis galioja ir n + 1.
• Iš šių dviejų žingsnių seka, kad teiginys galioja visiems natūraliems skaičiams.

Formali indukcijos struktūra

• Nurodykite, kad įrodymas bus atliekamas indukcijos būdu per n {\displaystyle n} . (n {\displaystyle n} yra indukcinis kintamasis.)
• 1) Pradinis žingsnis (base case): parodykite, kad teiginys teisingas, kai n {\displaystyle n} yra 1.
• 2) Indukcinė prielaida (inductive hypothesis): tarkime, kad teiginys teisingas už tam tikrą natūralųjį skaičių n {\displaystyle n}.
• 3) Indukcinis žingsnis (inductive step): įrodykite, kad iš prielaidos, jog teiginys galioja n, seka jog teiginys galioja ir n + 1 {\displaystyle n+1}.

Jei pradinis žingsnis įvykdomas ir indukcinis žingsnis įrodomas, tai teiginys galioja visiems natūraliems skaičiams: pirmiausia turime 1, tada pagal indukciją galioja 2, iš 2 seka 3, ir taip toliau.

Pavyzdys: skaičių 1+2+...+n suma

Įrodykime, kad visiems natūraliesiems skaičiams n galioja formulė

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

Įrodymas indukcija (vienas iš įprastų variantų):

1. Pradinis žingsnis (n = 1):
   Patikrinkime formulę n = 1 atveju:

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

   Taigi formulė teisinga n = 1 atveju.
2. Indukcinė prielaida:
   Tarkime, kad formulė teisinga už tam tikrą n = n0:

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

3. Indukcinis žingsnis:
   Rodykime, kad tada formulė teisinga ir n = n0 + 1 atveju. Pradėkime nuo kairės pusės:

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

   Galime perrašyti sumą kaip anksčiau turėtos sumos ir papildymo vienu nariu:

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

   Pagal indukcinę prielaidą pakeičiame 2∑_{k=1}^{n0}k išraiška:

   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 ∑ 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)}

   Padaliję iš 2, gauname reikiamą formą:

   ∑_{k=1}^{n0+1} k = (n0+1)(n0+2)/2, t. y. formulė galioja ir n = n0 + 1 atveju.

Taigi pradinis žingsnis ir indukcinis žingsnis užtikrina, kad teiginys teisingas visiems natūraliesiems skaičiams. Įrodymas yra baigtas.

Pastabos, variacijos ir patarimai

• Stiprioji indukcija: kartais naudinga manyti prielaidą, jog teiginys galioja visiems mažesniems nei n skaičiams, ir remiantis tuo įrodyti atvejį n+1. Tai vadinama stipriąja indukcija ir matematiškai ekvivalentiška įprastinei indukcijai, bet praktiškai patogesnė tam tikroms problemoms (pvz., dalijamumo savybėms, Fibonacci tipo eilutėms).
• Dažnos klaidos:
  • Neaiškus arba praleistas pradinio žingsnio patikrinimas.
  • Indukcinio žingsnio klaida: neaiškus, kaip prielaida naudojama naujame žingsnyje arba pamirštama parodyti, kad iš prielaidos tikrai seka reikalingas teiginys.
  • Neteisingas kintamojo nustatymas (pvz., praleidimas apie tai, už kokių n teiginys laikomas teisingu).
• Praktiniai patarimai: visuomet aiškiai pažymėkite pradinį atvejį ir įrašykite indukcinę prielaidą su atitinkamu n0. Rinkdamiesi indukcijos procedūrą, pagalvokite, ar norite tiesioginės indukcijos (iš n į n+1) ar stipriosios indukcijos.

Apibendrinimas

Matematinė indukcija yra galingas ir formalus metodas, leidžiantis per bazinį atvejį ir indukcinį žingsnį apimti begalinį skaičių atvejų vienu nuosekliu argumentu. Ji taikoma algebrai, kombinatorikai, skaičių teorijai ir daugelyje kitų sričių, kuriose reikia parodyti tvirtinimų galiojimą visiems natūraliems skaičiams.

Klausimai ir atsakymai

K: Kas yra matematinė indukcija?

K: Kaip vyksta indukcinis įrodymas?

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

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

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

Paieška pagal raidę