Kasutaja:Sungamerglav/Matemaatiline induktsioon

Matemaatilist induktsiooni saab illustreerida näiteks doominoefektiga.

Matemaatiline induktsioon on matemaatilise tõestuse tehnika. Seda kasutatakse tõestamiseks, et omadus P(n) kehtib kõikide naturaalarvude 0, 1, 2, 3... puhul. Et mõista matemaatilise induktsiooni kontseptsiooni, võib abi olla langevate doominode või redelil ronimise metafoorist:

„Matemaatiline induktsioon tõestab, et saame redelil tõusta nii kõrgele, kui me ise tahame. Selleks peame tõestama, et saame astuda esimesele astmele (baas) ja sealt edasi igale järgmisele astmele (samm).“

– Concrete Mathematics, lehekülg 3 ääremärkused.

Induktsioon puhul on vaja tõestada kahte juhtu. Esimest juhtu nimetatakse baasjuhuks, mis tõestab, et omadus kehtib arvule null. Teine juhtum, mida nimetatakse induktsiooni sammuks, tõestab, et juhul, kui omadus kehtib naturaalarvule n, siis kehtib see ka järgmisele naturaalarvule n+1. Need kaks juhtu kehtestavad omaduse P(n) kõik naturaalarvude n = 0, 1, 2, 3... puhul. Baas ei pea algama nullist.. Sageli see algab number ühest ja see võib alati ükskõik millisest naturaalarvust tõestamaks, et see omadus kehtib kõikidele arvudele, mis on võrdsed või suuremad sellest arvust.

Kuigi nimi võib sellele viidata, ei tohiks matemaatilist induktsiooni segi ajada induktiivse arutlusega, mida kasutatakse filosoofias (vaata ka Induktsiooniprobleem). Matemaatiline induktsioon on järeldusreegel , mida kasutatakse formaalsetes tõestustes. Tõestused matemaatilise induktsiooni abil on tegelikult näited deduktiivsetest arutluskäikudest.

Kirjeldus

Kõige lihtsam ja levinum matemaatilise induktsiooni vorm tuleneb sellest, et väide, mis kehtib naturaalarvu n puhul, kehtib kõigi arvu n väärtuste puhul. Tõestus koosneb kahest etapist:

1. Baas: tõestame, et väide kehtib esimese naturaalarvu n puhul. Tavaliselt n = 0 või n = 1. Harva, aga mõnikord on mugav võtta baasväärtus n võrduma mõne suurema numbriga või isegi negatiivse numbriga (väide kehtib ainult selle ja sellest suuremate arvude puhul), sest see ei sega täieliku järjestuse omadust.
2. Samm: eeldame, et väide kehtib mõne naturaalarvu n puhul ja tõestame, et väide kehtib ka n + 1 puhul.

Eeldust induktsiooni sammus, et väide kehtib mingi arvu n puhul, nimetatakse induktsiooni hüpoteesiks. Et tõestada induktsiooni sammu, peame eeldama, et induktsiooni hüpotees kehtib ja seejärel kasutame seda väidet, et tõestada kehtivus n + 1 puhul.

Näide

Matemaatilise induktsiooni abil saame tõestada, et järgmine avaldis, P(n), kehtib kõikide naturaalarvude n puhul.${\displaystyle }$$0+1+2+\cdots +n={\frac {n(n+1)}{2}}$.

P(n) annab valemi, millega arvutada kõikide naturaalarvude summa, mis on  väiksemad või võrdsed arvuga n. Tõestus, et P(n) kehtib naturaalarvu n puhul on järgmine.${\displaystyle }$Baas: Näitame, et väide kehtib n = 0 puhul. On lihtne näha, et P(0) on tõsi:

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

Samm: Näitame, et kui P(k) kehtib, siis ka P(k + 1) kehtib. Seda saab teha järgmiselt.Oletame, et P(k) kehtib (mõnel määramata k väärtusel). Seejärel tuleb näidata, et P(k + 1) kehtib:${\displaystyle }$$(0+1+2+\cdots +k)+(k+1)={\frac {(k+1)((k+1)+1)}{2}}.$${\displaystyle }$Kasutades induktsiooni oletust, et P(k) kehtib, saame võrduse vasaku poole ümber kirjutada järgnevalt:

${\frac {k(k+1)}{2}}+(k+1)\,.$${\displaystyle }$Algebraliselt:

${\begin{aligned}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)}{2}}\end{aligned}}$

näidates seeläbi, et tõepoolest P(k + 1) kehtib.

Kuna nii baas kui ka samm on teostatud, oleme matemaatilise induktsiooni abiga tõestanud, et P(n) kehtib kõikide naturaalarvude n puhul. M.O.T.T.

Tugev induktsioon

Üks matemaatilise induktsiooni variante, mida nimetatakse tugevaks induktsiooniks, muudab induktsiooni sammu tõestamise hõlpsamaks selle läbi, et kasutab tugevamat hüpoteesi tõestada, kasutades tugevama hüpoteesi. Me tõestame väidet P(m + 1) eeldusel, et P(n) kehtib kõikide naturaalarvude n puul, mis on väiksemad, kui m +1. Tavalise induktsiooni puhul eeldame vaid, et kehtib p(m). Nimi "tugev induktsioon" ei tähenda, et see meetod võib mõnda väidet tõendada tugevamini kui tavaline induktsioon, vaid üksnes viitab tugevamale hüpoteesile, mida kasutatakse induktsiooni sammus. Tegelikkuses on need kaks meetodit samaväärsed.

Näide: Fibonacci numbrid

${\displaystyle }$Tugev induktsioon on kasulik, kui on vaja kasutada mitut erinevat induktsiooni hüpoteesi juhtu iga induktsiooni sammu puhul. Näiteks saab tugevat induktsiooni kasutada, et näidata

$F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}$,

kus F_n on n-is Fibonacci arv, φ = (1 + √5 )/2 (Kuldlõige) ja ψ = (1 − √5 )/2 on polünoomi x² − x − 1 juured. Kasutades asjaolu, et F_n+2 = F_n+1 + F_n iga n ∈ N puhul, saame kontrollida võrdsuse kehtivust, arvutades otse välja F_n+2, kui eeldame, et kehtivad F_n+1 ja F_n. Et tõestus lõpetada, peame tõestama, et võrdus kehtib ka kahel baasjuhul: n = 0 ja n = 1.

Näide veast induktsiooni sammu juures

Induktsiooni samm peab olema tõendatud kõikide n-i väärtuste juures. Et seda illustreerida, on Joel E. Cohen kavandatud järgmised argument, mida püütakse tõestada matemaatilise induktsiooni, et kõik hobused on sama värvi:

• Baas: Hulgas, kus on üks hobune, on vaid üks värv.
• Samm: Eeldame, nagu induktsiooni baasis, et igas hulgas , kus on n hobust, on ka ainult üks värv. Nüüd vaatame kõiki n + 1 hobuste hulki. Nummerdame need: 1, 2, 3, ..., n, n + 1. Vaatleme lähemalt hulki {1, 2, 3, ..., n} ja {2, 3, 4, ..., n + 1}. Mõlemas hulgas on n hobust, seega mõlemas hulgas on ainult üks värv. Kuna hulgad kattuvad, siis peab  igas hulgas, kus on n + 1 hobust, olema ainult ühte värvi hobused.

Baasjuht n = 1 on triviaalne (iga hobune on sama värvi nagu ta ise) ja induktsiooni samm on õige igal n > 1 juhul. Viga peitub induktsiooni sammus n = 1, sest väide, et kaks hulka kattuvad, on vale. Hulgas n + 1 on kaks hobust ning esimese ja viimase eemaldamisel saame kaks hulka, millel puudub ühisosa.

Vaata ka

• Rekursioon