Šis tas apie matematinę indukciją

Visiems turbūt pažįstama situacija, kai šalia vienas kito pastatomi domino kauliukai ir iš jų sudaroma grandinėlė. Tuomet  viename grandinėlės gale esantis kauliukas nuverčiamas, šis krisdamas nuverčia sekantį ir taip toliau, kol nuvirsta paskutinis kauliukas.
Tarkime mums duota viena domino kauliukų grandinėlė, o mūsų prašoma įrodyti, jog nuvertus viename gradinėlės gale esantį kauliuką nuvirs bet kuris kitas kauliukas. Šią užduotį galėtume įveikti taip:

Sunumeruojame visus kauliukus iš eilės nuo 1 pradedant tuo, kuris bus pirmiausiai nuverčiamas.

1) Pirmiausiai įrodykime, jog bandant nuversti pirmąjį kauliuką, jis nukris.
2) Tuomet padarykime prielaidą (spėjimą), jog gali būti nuverčiamas bet kuris kauliukas, kurio eilės numeris yra k∈N.
3) Remiantis šia prielaida bandykime įrodyti, jog galime nuversti ir kauliuką, kurio eilės numeris k+1.

Įvykdžius visas šias tris sąlygas mes įrodytume, jog nuvirs bet kuris grandinėje esantis kauliukas net jei jų skaičius begalinis.

Šis pavyzdys gerai iliustruoja matematinės indukcijos, kuria remiamasi įrodant tam tikrus teiginius, esmę. Bendru atveju įrodymas matematinės indukcijos pagalba yra nusakomas taip:

Tarkime turime įrodyti teiginio [tex]T(n)[/tex] tesingumą su visomis kai [tex]n∈N[/tex] reikšmėmis.
1) Patikriname, ar šis teiginys [tex]T(n)[/tex] teisingas, kai [tex]n=1[/tex].
2) Darome prielaidą, jog teiginys [tex]T(n)[/tex] teisingas, kai [tex]n=k[/tex]
3) Įrodyti, jog jei teisingas teiginys [tex]T(k)[/tex], tai teisingas ir teiginys [tex]T(k+1)[/tex]

Atlikime kelias užduotis:
1. Įrodykite, jog [tex]n^3-n[/tex] yra dalus iš 6 su visomis [tex]n∈N[/tex] reikšmėmis.
Įrodymas:
Turime teiginį: [tex]T(n)[/tex] - "[tex]n^3-n[/tex] yra dalus iš 6"
1) Kai [tex]n=1[/tex], tai [tex]n^3-n=1^3-1=0[/tex], 0 dalijasi iš 6, vadinasi teiginys [tex]T(1)[/tex] teisingas.
2) Darome prielaidą, jog teiginys [tex]T(k)[/tex] - teisingas, t.y., kad [tex]k^3-k[/tex] dalijasi iš 6.
3) Įrodykime, jog teisingas teiginys [tex]T(k+1)[/tex]:
Reiškinys [tex]n^3-n[/tex], kai [tex]n=k+1[/tex] lygus: $$(k+1)^3-(k+1)=k^3+3k+3k^2+1-k-1=\\k^3+2k+3k^2=k^3-k+3k+3k^2=k^3-k+3k(1+k).$$ [tex]k^3-k[/tex] dalijasi iš 6 pagal prielaidą. Tuo tarpu [tex]3k(1+k)[/tex] dalijasi iš 6, nes sandauga [tex]3k(1+k)[/tex] dalijasi iš 2 ir 3. Iš 2 dalijasi, nes [tex]k(1+k)[/tex] dalijasi iš 2 (vienas iš dviejų gretimų natūraliųjų skaičių yra lyginis, todėl jų sandauga yra lyginis skaičius). Iš 3 dalijasi, nes sandaugoje [tex]3k(1+k)[/tex] yra dauginamasis 3. Jei sumos dėmenys dalijasi iš 6, tai ir visa suma dalijasi iš 6.

Apibendriname: Įrodėme, jog teisingas teiginys [tex]T(1)[/tex]. Padarėme prielaidą, jog teisingas teiginys, kai [tex]T(k)[/tex]. Remiantis šia prielaida įrodėme, jog teisingas teiginys [tex]T(k+1)[/tex]. Vadinasi [tex]n^3-n[/tex] dalijasi iš 6 su visomis natūraliomis [tex]n[/tex] reikšmėmis.

2. Įrodykite, jog teisinga lygybė: [tex]1\cdot 2+2\cdot 3+3\cdot 4+...+(n-1)n=\dfrac{(n-1)n(n+1)}{3}[/tex]
Įrodymas
1) Remdamiesi formule tikriname jos teisingumą pradėdami ne nuo [tex]n=1[/tex], o nuo [tex]n=2[/tex], nes pirmasis sumos dėmuo yra [tex](2-1)\cdot 2[/tex].
Svarbu paminėti, jog yra tokių atvejų (kaip ir šiuo duotuoju), kai tikrinant teiginio T(n) teisingumą su n=1, galime gauti, jog jis neteisingas arba jo teisingumo nustatyti neįmanoma, tada imama sekanti reikšmė, jei ir ši netinka, dar kita, kol galiausiai randama tinkama reikšmė. Taip nežymiai pakeitę pirmąjį įrodymo punktą taikome nepakitusius antrąjį ir trečiąjį. Gauname: [tex]\dfrac{(2-1)\cdot 2\cdot (2+1)}{3}=2=1\cdot 2[/tex]. Teiginys teisingas.
2) Darome prielaidą, jog teisingas teiginys:
[tex]1\cdot 2+2\cdot 3+3\cdot 4+...+(k-1)k=\dfrac{(k-1)k(k+1)}{3}[/tex]
3) Remiantis prielaida įrodykime, jog teisingas teiginys:
[tex]1\cdot 2+2\cdot 3+3\cdot 4+...+(k+1-1)(k+1)=\dfrac{(k+1-1)(k+1)(k+1+1)}{3}[/tex], t.y.:
[tex]1\cdot 2+2\cdot 3+3\cdot 4+...+k(k+1)=\dfrac{k(k+1)(k+2)}{3}[/tex]
Gauname:
Pasinaudoję prielaida sumą [tex]1\cdot 2+2\cdot 3+3\cdot 4+...+k(k+1)[/tex] galime užrašyti taip:
$$1\cdot 2+2\cdot 3+3\cdot 4+...+(k-1)k+k(k+1)=\dfrac{(k-1)k(k+1)}{3}+k(k+1)=\\\dfrac{(k-1)k(k+1)+3k(k+1)}{3}=
\dfrac{(k+1)(k(k-1)+3k)}{3}=\dfrac{(k+1)(k^2+2k)}{3}=\\\dfrac{(k+1)\cdot k(k+2)}{3}=\dfrac{k(k+1)(k+2)}{3}$$ Gavome tai, ką ir turėjome įrodyti, vadinasi lygybė teisinga, kai [tex]n>1, n∈N[/tex].

3. Įrodykite, jog teisinga nelygybė: [tex]\dfrac{1}{n+1}+\dfrac{1}{n+2}+\dfrac{1}{n+3}+...+\dfrac{1}{2n}>\dfrac{13}{24}[/tex]
Įrodymas:
1) Kai [tex]n=1[/tex], gauname, kad: [tex]\dfrac{1}{1+1}=\dfrac{1}{2}<\dfrac{13}{24}[/tex]
Kai [tex]n=2[/tex], gauname, kad: [tex]\dfrac{1}{2+1}+\dfrac{1}{2\cdot 2}=\dfrac{1}{3}+\dfrac{1}{4}=\dfrac{14}{24}>\dfrac{13}{24}[/tex]
2) Darome prielaidą, jog teisinga nelygybė: [tex]\dfrac{1}{k+1}+\dfrac{1}{k+2}+\dfrac{1}{k+3}+...+\dfrac{1}{2k}>\dfrac{13}{24}[/tex]
3) Įrodykime, jog teisinga nelygybė: [tex]\dfrac{1}{k+1+1}+\dfrac{1}{k+1+2}+\dfrac{1}{k+1+3}+...+\dfrac{1}{2(k+1)}>\dfrac{13}{24}[/tex], t.y.:
[tex]\dfrac{1}{k+2}+\dfrac{1}{k+3}+\dfrac{1}{k+4}+...+\dfrac{1}{2(k+1)}>\dfrac{13}{24}[/tex]
Supaprastindami įrodymą pažymėkime sumą: [tex]S(n)=\dfrac{1}{n+1}+\dfrac{1}{n+2}+\dfrac{1}{n+3}+...+\dfrac{1}{2n}[/tex].
Gauname, kad:
$$S(k+1)=S(k)-\dfrac{1}{k+1}+\dfrac{1}{2k+1}+\dfrac{1}{2k+2}=\\S(k)+\dfrac{-(2k+1)(2k+2)+(k+1)(2k+2)+(k+1)(2k+1)}{(k+1)(2k+1)(2k+2)}=\\S(k)+\dfrac{1}{2(2k+1)(k+1)}$$
Kadangi [tex]S(k)>\dfrac{13}{24}[/tex] pagal prielaidą, o [tex]\dfrac{1}{2(2k+1)(k+1)}>0[/tex], nes vardiklis teigiamas su visomis [tex]k>1[/tex] reikšmėmis, tai [tex]S(k+1)>\dfrac{13}{24}[/tex]. Įrodėme nelygybės teisingumą su visomis [tex]n>1, n∈N[/tex] reikšmėmis.