Matemātiskā indukcija

Matemātisko indukciju neformāli var attēlot, izmantojot krītošus domino kauliņus.

Matemātiskā indukcija ir pierādīšanas tehnika matemātikā. To parasti izmanto, lai pierādītu, ka kāds apgalvojums vai īpašība ir spēkā visiem naturālajiem skaitļiem.

Matemātiskā indukcija izmanto šādu principu — ja mēs zinam par kādu apgalvojumu A(n), kas ir definēts visiem naturālajiem skaitļiem n, ka:

1. A(1) ir patiess;
2. katram naturālam skaitlim k ir spēkā tas, ka, ja A(k) ir patiess, tad arī A(k+1) ir patiess,

tad var secināt, ka apgalvojums A(n) ir patiess visiem naturālajiem skaitļiem — no 1. punkta ir redzams, ka A(1) ir patiess. No 2. punkta var secināt, ka tā kā A(1) ir patiess, tad arī A(2) ir patiess. Atkārtoti izmantojot 2. punktu, var secināt, ka tā kā A(2) ir patiess, tad arī A(3) ir patiess. Šo procesu (2. punkta izmantošanu) var turpināt bezgalīgi, tāpēc ir iespējams izdarīt secinājumu, ka apgalvojums ir spēkā visiem naturālajiem skaitļiem.

Parasti kāda apgalvojuma A(n) pierādīšanu pēc matemātiskās indukcijas principa veic pēc šāda algoritma.

1. Indukcijas bāze — pamato, ka apgalvojums ir patiess pie n=1. Šajā gadījumā skaitli 1 sauc par indukcijas bāzi.
2. Induktīvais pieņēmums — tiek pieņemts, ka apgalvojums ir patiess pie n=k, kur k — jebkurš naturāls skaitlis.
3. Induktīvā pāreja — pamato, ka, ja ir spēkā induktīvais pieņēmums, apgalvojums ir spēkā arī pie n=k+1.
4. Secinājums — pēc matemātiskās indukcijas principa var secināt, ka apgalvojums ir spēkā visiem naturālajiem skaitļiem.

Pirmās zināmās matemātiskās indukcijas pēdas ir manāmais Eiklīda pierādījumā, ka ir bezgalīgi daudz pirmskaitļu. Tomēr pirmais, kas formulējis matemātiskās indukcijas principu, bija Blēzs Paskāls savā darbā Traité du triangle arithmétique.

Varianti

Atkarībā no tā, ko ir nepieciešams pierādīt, realitātē matemātiskās indukcijas princips var tikt izmantots atšķirīgi no dotā algoritma.

• Par indukcijas bāzi var izmantot ne tikai skaitli 1, bet arī jebkuru citu naturālu skaitli. Plašāk izmantotās indukcijas bāzes ir 1 un 0. Jāņem vērā, ka, ja ir izmantota bāze, kas atšķirīga no 1, apgalvojums tiek pierādīts visiem veselajiem skaitļiem, kas lielāki vai vienādi par indukcijas bāzi. Induktīvajā pieņēmumā skaitlim k ir jābūt lielākam vai vienādam par indukcijas bāzi. Piemēram, indukciju ar bāzi 3 var izmantot, lai pierādītu, ka 2ⁿ≥n+5, ja n≥3.
• Indukcijā var tikt izmantota vairāk nekā viena bāze.
• Indukcija var tikt veikta pēc vairāk nekā viena mainīgā. Ja ir jāpierāda apgalvojums, kas ir atkarīgs no diviem naturāliem skaitļiem — n un m. Šajā gadījumā vispirms tiek pierādīta indukcijas bāze un induktīvā pāreja pēc n, tad pie katra no n pierāda indukcijas bāzi un induktīvo pāreju pēc m.
• Induktīvās pārejas sakarība var atšķirties no pierastā n=k+1. Piemēram, var būt apgalvojums, ko pierāda visiem naturāliem skaitļiem, izmantojot par bāzēm n=1 un n=2, bet induktīvajā pārejā pierādot, ka, ja apgalvojums ir spēkā pie n=k, tad apgalvojums ir spēkā arī pie n=k+2. Ja ir jāpierāda apgalvojums, kas ir spēkā visiem veseliem negatīviem skaitļiem, var izmantot sakarību n=k-1 — veikt indukciju pretējā virzienā. Ja ir jāpierāda apgalvojums, kas ir spēkā visām divnieka pakāpēm, var izmantot sakarību n=2*k.
• Indukciju var veikt vairākas reizes, mainot arī indukcijas virzienu. Piemēram, lai pierādītu apgalvojumu visiem veseliem skaitļiem, var veikt standarta indukciju, par bāzi izmantojot skaitli 0, tādējādi pierādot to visiem veseliem nenegatīviem skaitļiem, bet pēc tam var veikt indukciju "pretējā virzienā", pierādot apgalvojumu visiem veseliem negatīvajiem skaitļiem. Ogistēns Košī pierādīja nevienādību starp vidējo aritmētisko un vidējo ģeometrisko, vispirms ar indukciju pierādot, ka apgalvojums ir spēkā visām divnieka pakāpēm, un tad veica indukciju pretējā virzienā, pierādot to visiem naturāliem skaitļiem.
• Dažubrīd induktīvais pieņēmums nav pietiekami spēcīgs. Šādos gadījumos var izmantot citu, spēcīgāku induktīvo pieņēmumu — pieņem, ka apgalvojums ir patiess pie visiem n, kas ir mazāki vai vienādi par k, kur k — jebkurš naturāls skaitlis. Šādu paņēmienu sauc par pilno indukciju.
• Bezgalīgā kritiena metodi var uzskatīt par matemātiskās indukcijas variantu. Šo metodi izmanto, lai pierādītu, ka kāds apgalvojums A(n) ir aplams visiem naturāliem skaitļiem. Tiek pierādīts, ka, ja apgalvojums ir spēkā kādam naturālam skaitlim n, tad tas ir spēkā arī mazākam naturālam skaitlim k. Tā kā neeksistē bezgalīga dilstoša naturālo skaitļu virkne, ir iegūta pretruna un var secināt, ka pieņēmums ir aplams.

Piemērs

Šajā piemērā tiks pierādīts šāda vienādība (formula visu naturālo skaitļu, kas mazāki par n, summai):

$1+2+3+...+n={\frac {n(n+1)}{2}}.$

Vispirms pierāda indukcijas bāzi — to, ka šāda vienādība ir spēkā tad, ja n=1:

$1={\frac {1*2}{2}}=1.$

Induktīvais pieņēmums: pieņem, ka dotā vienādība ir spēkā pie n=k:

$1+2+3+...+k={\frac {k(k+1)}{2}}.$

Induktīvā pāreja: pierādīsim, ka dotā vienādība ir spēkā arī pie n=k+1:

$1+2+3+...+k+k+1={\frac {(k+1)(k+2)}{2}}.$

No induktīvā pieņēmuma mēs zinam, ka $1+2+3+...+k={\frac {k(k+1)}{2}}.$ To var ievietot pierādāmajā:

$k+1+{\frac {k(k+1)}{2}}={\frac {(k+1)(k+2)}{2}}$

$k+1={\frac {(k+1)(k+2)}{2}}-{\frac {k(k+1)}{2}}={\frac {(k+1)(k+2)-k(k+1)}{2}}={\frac {k^{2}+3k+2-k^{2}-k}{2}}={\frac {2k+2}{2}}=k+1$

Esam pierādījuši gan indukcijas bāzi, gan induktīvo pieņēmumu. Tātad pēc matemātiskās indukcijas principa var secināt, ka dotā vienādība ir spēka visiem naturāliem n.

Aplams piemērs

Veicot matemātisko indukciju ir jābūt uzmanīgam, lai netiku pieļauta kļūda, pretējā gadījumā var tikt pierādīti acīmredzami aplami apgalvojumi. Šajā piemērā tiks kļūdaini pierādīts, ka visi zirgi ir vienā krāsā.

• Indukcijas bāze — jebkurā kopā, kas sastāv no viena zirga ir tikai vienas krāsas zirgi. Šis apgalvojums ir acīmredzami patiess.
• Induktīvais pieņēmums — jebkurā kopā ar n zirgiem ir tikai vienas krāsas zirgi.
• Induktīvā pāreja — pierādīsim, ka jebkurā kopā ar n+1 zirgiem ir tikai vienas krāsas zirgi. Apzīmēsim zirgus šajā kopā ar {1, 2, 3, ..., n, n+1}. Aplūkosim kopas {1, 2, ..., n} un {2, 3, ..., n+1}. Abās šajās kopās ir n zirgi, tātad katrā šajā kopā visi zirgi ir vienā krāsā. Šīs divas kopas pārklājas, tāpēc var secināt, ka visi n+1 zirgi ir vienā krāsā.

Esam šķietami pierādījuši, izmantojot matemātikas indukcijas principu, ka visi zirgi ir vienā krāsā, kas liekas acīmredzami aplami. Kā indukcijas bāzi mēs esam paņēmuši n=1, kā arī induktīvā pāreja ir patiesa visiem n>1. Kļūda radās tāpēc, ka induktīvā pāreja nav patiesa pie n=1 (abās aplūkotajās kopās ir tikai viens zirgs, līdz ar to tās nepārklājas). Tāpēc matemātiskās indukcijas principu šajā gadījumā pielietot nevar.