Teorija

Šajā tematā vispārīgus apgalvojumus vai uzdevumus apzīmē ar lielajiem latīņu burtiem (\(A, B, C\) utt.), aiz tiem iekavās norāda apgalvojuma vai uzdevuma parametrus.
Piemēram, uzdevumu "atrast, cik veidos naturālu skaitli \(n\) var izteikt ar vieninieku un divnieku summu",  apzīmē ar  \(B(n). \)
 Konkrēto uzdevumu, kurā \(n\) ir piešķirta kāda vērtība (piemēram, ja \(n=12\)), apzīmē ar \(B(12\)), kas nozīmē  "atrast, cik veidos naturālu skaitli \(12\) var izteikt ar vieninieku un divnieku summu".
 
Matemātiskās indukcijas princips (MIP)
Ja
1) apgalvojums \(A(1\)) ir patiess,
2) katram naturālam \(k\) no tā, ka patiess ir apgalvojums \(A(k\)), izriet apgalvojuma \(A(k+1)\) patiesums,
tad
apgalvojums \(A(n)\) ir patiess visiem naturāliem skaitļiem \(n\).
Izmantojot MIP, pierādījumu, ka \(A(n)\) ir patiess, veic pēc sekojoša algoritma.
 
1) Indukcijas bāze. Pārbauda, vai ir patiess apgalvojums \(A(1).\)
2) Induktīvais pieņēmums (hipotēze). Pieņem, ka \(A(k)\) ir patiess.
3) Induktīvā pāreja. Pierāda, ka patiess ir arī apgalvojums \(A(k+1).\)
 
MIP ir viena no aritmētikas aksiomām, tāpēc tā pareizība nav jāpierāda.
 
MIP var ilustrēt ģeometriski.
 
 Apgalvojumu \(A(n\)) var attēlot ar rūtiņu rindu:
IMG00033.gif
 
Ja \(A(1)\) ir patiess, var aizkrāsot pirmo rūtiņu:
IMG00034.gif (indukcijas bāze)
 
Bet nosacījums 2) -3) ģeometriski nozīmē šādu pāreju:
labk.PNG (induktīvā pāreja)
 
Iegūst lenti, kurā aizkrāsotas pirmās divas rūtiņas: 
IMG00036.gif
Atkārtojot vēlreiz šādu pāreju- aizstājot rūtiņu kombināciju labkbez.png ar  rrrrrr.PNG, iegūstam lenti, kurā aizkrāsotas pirmās trīs rūtiņas: IMG00039.gif .
Līdzīgi turpinot, pakāpeniski aizkrāsojas visa bezgalīgā lenta, t.i., ir pierādīts vispārīgais apgalvojums \(A(n\)):  lenta.PNG (secinājums).
 
Atsauce:
http://www.lanet.lv/info/matind/mim-03.htm
Materiālu sagatavoja Mg. math. Laima Baltiņa, JTV skolotāja