Matemaatiline induktsioon: definitsioon, induktsioonisamm ja näited

Matemaatiline induktsioon on loogiline meetod väidete tõestamiseks, mis kehtivad kõigi (või alates mõnest algusest kõigi järgneva) naturaalarvude puhul. Põhiolemus on lihtne: kui suudame näidata, et väide kehtib lähtejuhtumi kohta ja et ühe arvu puhul kehtivus viib alati kehtivuseni järgmisel arvul, siis kehtib väide kõikide järgnevate arvude puhul. See toimib nagu dominoefekt: kui esimene klots langeb ja iga klotsi langemine paneb järgmise liikuma, siis langevad lõpuks kõik klotsid.

Induktsiooni standardne kaks sammu

• Baasjeis (algjuhtum): näita, et väide on tõene mingi algväärtuse kohta (tavaliselt n=1, kuid võib olla ka n=0 või muu sobiv algväärtus).
• Induktsioonisamm: eeldades, et väide on tõene mõne suvalise, kuid fikseeritud naturaalarvu n puhul (see eeldus nimetatakse induktsioonihüpoteesiks), näita, et sellest järeldub väite tõeväärtus ka arvule n+1.

Kui mõlemad sammud on õigesti tõestatud, siis kehtib väide kõigi vastavate naturaalarvude puhul: alates algväärtusest edasi iga samm viib järgmise õigeks, seega ka kõik järgnevad.

Mida täpselt "induktsioonimuutujaks" nimetatakse?

Induktsioonimuutuja on tavaliselt n — see on naturaalarv, mille kohta väidet tõendame. Mõnikord kirjutatakse seda matemaatilises tekstis ka kujul n {\displaystyle n}. Oluline on selgelt määratleda, millistele väärtustele induktsioon kehtib (näiteks kõigile naturaalarvudele alates 1-st või alates 0-st).

Induktsiooni samm ja selle loogika

• Baasjeis kontrollimine kinnitab, et ehkki induktsioonibeemari (järjestikuste järelduste ahel) algab, on algus olemas.
• Induktsioonihüpotees ehk oletus, et väide kehtib mingi suvalise, fikseeritud n {\displaystyle n} puhul, võimaldab meil tuletada väite kehtivuse ka n+1 {\displaystyle n+1} kohta.
• Selle kombinatsiooni tõttu levib tõde samm-sammult üle kõikide järgneva väärtuste.

Trikid ja tähelepanekud

• Algjuhtum ei pruugi alati olla n=1; mõnikord peab alustama näiteks n=0-st või mõnest muust arvust.
• On olemas ka tugev induktsioon (või täielik induktsioon), kus induktsioonihüpotees eeldab väite kehtivust kõigi väiksemate väärtuste kohta, et järeldada seejärel kehtivus järgmise väärtuse kohta. See on kasulik, kui vajate järelduseks rohkem kui lihtsalt eelmise sammu infot.
• Induktsioon ei "leiuta" tõestust — see ainult ühendab baasjeisu ja induktsioonisammu loogiliselt tervikuks; mõlemad peavad olema korrektsed.

Näide induktsioonitõestusest

Tõestame, et kõigi naturaalarvude n puhul kehtib võrdus

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)}

Kirjeldame tõestust samm-sammult:

Baasjeis: kui n = 1, siis vasakul pool on 1 ja paremal pool on

2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)}

seega avaldus on tõene baasjuhtumi jaoks.

Induktsioonihüpotees: oletame, et väide kehtib mingis fikseeritud naturaalarvus n = n0, s.t.

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)}

Induktsioonisamm: näitame, et sellega järgneb avalduse tõeväärtus ka n = n0 + 1 puhul. Kirjutame summa kuni n0+1 kujul

2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k}}

mida saab ümber kirjutada kui olemasolev summa kuni n0 pluss viimane liikmelisus:

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)}

Kuna induktsioonihüpoteesi kohaselt kehtib 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) , {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),}, asendades saame

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)}

Jagades mõlemad pooled kahega (või lihtsalt tõlgendades selle tulemusena saadud väljendit), näeme, et

{\displaystyle \sum_{k=1}^{n_{0}+1}k={\tfrac{1}{2}}(n_{0}+1)(n_{0}+2)}

see on täpselt sama kuju nagu pärisavalduse parempoolne osa, kuid n asendatud n0+1-ga. Seega induktsioonisamm õnnestus ja väide kehtib ka n0+1 puhul.

Kuna baasjeis on avaldus tõene (n=1) ja induktsioonisamm näitab, et suvalise n puhul kehtivus viib kehtivuseni n+1 puhul, siis kehtib antud avaldus kõikide naturaalarvude n kohta.

Kokkuvõte

• Matemaatiline induktsioon on võimas ja laialt kasutatav tööriist tõestamaks väiteid, mis sõltuvad naturaalarvustest.
• Oluline on korrektselt tuua välja baasjuhtum ja selgelt sõnastada ning õigesti kasutada induktsioonihüpoteesi induktsioonisammus.
• Praktikas aitab induktsiooni õppida mitmete konkreetsete näidete kaudu (summa-, korrutis- ja rekursiivsed jada-väited, omaduste ülekanne jpm).

Küsimused ja vastused

K: Mis on matemaatiline induktsioon?

K: Kuidas toimub tõendamine induktsiooni teel?

K: Mida tähendab induktiivses sammus millegi eeldamine?

K: Milliseid arvusid kasutatakse matemaatilises induktsioonis?

K: Kuidas näidata, et midagi on tõene järgmise arvu (n+1) puhul?

Otsing