Matematinė indukcija

Matematinė indukcija primena grandininę krentančių domino kauliukų reakciją: jei nuverčiame pirmą kauliuką ir kiekvienas kauliukas nuverčia kitą kauliuką, tai visi kauliukai bus nuversti.

Matematinė indukcija (lot. inductio – paskatinimas, įvedimas) – 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 kitas 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.

Manoma, kad 370 m. pr. m. e. Platono veikale „Parmenidas“ galima rasti ankstyvąjį matematinės indukcijos įrodymo pavyzdį.

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:

1. Į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į.
2. Į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:

1. Pirmas domino kauliukas nuvirs
2. 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

$0+1+2+\cdots +n={\frac {n(n+1)}{2}}$

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)):

$0={\frac {0\cdot (0+1)}{2}}\,.$

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į:

${\frac {0\cdot (0+1)}{2}}\,={\frac {0\cdot 1}{2}}\,={\frac {0}{2}}\,=0$

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 P(n + 1) 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 P(n + 1), kurį galima išreikšti lygybe

$0+1+2+\cdots +n+(n+1)={\frac {(n+1)((n+1)+1)}{2}}$

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

$(0+1+2+\cdots +n)+(n+1)={\frac {(n+1)((n+1)+1)}{2}}$

į

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

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

${\begin{aligned}{\frac {n(n+1)}{2}}+(n+1)&=(n+1)\left({\frac {n}{2}}+1\right)\\&=(n+1)\left({\frac {n}{2}}+{\frac {2}{2}}\right)\\&=(n+1)\left({\frac {n+2}{2}}\right)\\&={\frac {(n+1)(n+2)}{2}}\\&={\frac {(n+1)((n+1)+1)}{2}}.\end{aligned}}$

Tai įrodo, kad teiginys P(n + 1) 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

Vikižodynas