Matematinė indukcija

Matematinė indukcija yra matematinio įrodinėjimo metodas, dažniausiai naudojamas, kai reikia parodyti, kad koks nors teiginys yra teisingas visiems natūraliesiems skaičiams. Pirmas indukcijos etapas yra įrodyti, kad pirmasis teiginys iš begalinės teiginių sekos yra teisingas. Antrasis etapas yra įrodyti, kad jei vienas teiginys yra teisingas, tai ir sekantis teiginys begalinėje sekoje yra teisingas. Taip yra parodoma, kad visi sekos teiginiai pradedant pirmu yra teisingi. 

Matematinės indukcijos metodas gali būti ir praplėstas labiau apibendrintų sąvokų įrodymams. Tai vadinama struktūrine indukcija. Ji yra naudojama matematinėje logikoje bei kompiuterių moksle ir yra glaudžiai susijusi su rekursija.

Matematinė indukcija neturėtų būti painiojama su indukciniu samprotavimo metodu, kuris yra kritikuojamas, nes jo rezultatais niekada negalima tvirtai pasitikėti. Matematinė indukcija yra, priešingai, griežtas ir patikimas įrodinėjimo metodas ir iš tikrųjų yra dedukcinio mąstymo forma.

Aprašymas 
Paprasčiausia ir dažniausiai naudojama matematinės indukcijos forma įrodo, kad koks nors teiginys, kuriame yra natūralusis skaičius n yra teisingas visoms n reikšmėms. Tai yra padaroma dviem etapais:
 Įrodoma, kad teiginys yra teisingas, kai n = 0 arba n = 1. Tai padaroma vietoje n teiginyje įsistačius atitinkamai 0 arba 1 ir įrodžius gautą reiškinį.
 Įrodoma, kad jeigu teiginys yra teisingas kokiam nors natūraliajam skaičiui n, tai jis yra teisingas ir sekančiam natūraliajam skaičiui n + 1. Tai padaroma teiginyje vietoje n įsistatant n + 1 ir įrodant gautą reiškinį.

Tarkime, kad aprašytu būdu įrodėme kokį nors teiginį, pirmame etape įrodę, kad jis yra teisingas su n = 1. Tai reikštų, kad antrame etape įrodėme, jog reiškinys galioja ir su n + 1. Laikykime, kad čia n = 1. Tada n + 1 reikšmė yra n + 1 = 1 + 1 = 2. Taigi teiginys galioja skaičiumi 2 arba, kitaip tariant, kai n = 2. Kadangi teiginys yra teisingas su n = 2, tai jis yra teisingas ir su n + 1, kurio reikšmė šiuo atveju jau yra n + 1 = 2 + 1 = 3 . O kadangi teiginys teisingas su n = 3, tai dėl tos pačios priežasties jis yra teisingas ir su n = 4 ir t. t. iki begalybės.

Analogiška situacija yra su krintančiai domino kauliukais. Tarkime, kad turime ilgą domino kauliukų eilę ir žinome kad:
 Pirmas domino kauliukas nuvirs
 Nukritus bet kuriam domino kauliukui nukris ir jo kaimynas.

Galime būti tikri, kad galiojant šioms taisyklėms būtinai nuvirs visi domino kauliukai.

Pavyzdys 
Šiame pavyzdyje matematinės indukcijos metodu bus įrodyta, kad teiginys 

galioja visiems natūraliesiems skaičiams n. Pavadinkime tai teiginiu P(n).

Pirmasis etapas 
Reikia parodyti, kad teiginys yra teisingas, kai n = 0 (arba, kitaip tariant, įrodyti P(0)):

Kairiosios rankos lygybės pusė yra tiesiog lygi 0. 
Dešiniosios rankos lygybės pusėje turime reiškinį 0·(0 + 1)/2. Išsprendžiame jį: 

Kadangi abi lygybės pusės lygios nuliui, teiginys P(0) yra teisingas.

Antrasis etapas 
Reikia įrodyti, kad jeigu P(n) yra teisingas, tai ir  yra teisingas.

Visų pirma, reikia padaryti prielaidą, kad P(n) yra teisingas (kokiai nors neapibrėžtai reikšmei n). Po to reikia parodyti, kad tada ir teisingas yra ir , kurį galima išreikšti lygybe

Pasinaudojus indukcijos hipoteze P(n) (kurią ir bandome įrodyti), kairiosios rankos lygybės pusę galima perrašyti iš

į

Šią lygybę galima įrodyti tokiais algebriniais veiksmais:
 

Tai įrodo, kad teiginys  yra teisingas. Kadangi atlikti abu indukcijos etapai, įrodėme, kad teiginys P(n) yra teisingas visiems natūraliesiems skaičiams n, ką ir reikėjo padaryti.

Nuorodos 

Matematinė logika