Matemaatiline induktsioon

Mõiste

Matemaatiline induktsioon on tõestusviis väidetele, mis sõltuvad naturaalarvust $n$.

Eeldus: oskad lugeda väiteid kujul $P(n)$, teha algebralisi teisendusi ja kasutada jadade summasid.

Intuitsioon on nagu doominorida:

• esimene doomino kukub;
• iga doomino lükkab järgmise ümber.

Kui mõlemad tingimused kehtivad, kukuvad kõik doominod. Induktsioonis tähendab see:

• väide kehtib esimese $n$ väärtuse jaoks;
• kui väide kehtib mingi $n$ jaoks, siis kehtib see ka $n+1$ jaoks.

Skeem

1. Baassamm: tõesta väide esimese väärtuse jaoks.
2. Induktsioonisamm: eelda, et väide kehtib $n$ korral, ja tõesta, et siis kehtib see $n+1$ korral.

Induktsioonisammus ei tõestata väidet uuesti nullist. Seal kasutatakse induktsioonieeldust.

Kui väidet tähistada $P(n)$, siis tõestuse kuju on:

$$P(1)\quad\text{ja}\quad P(n)\Rightarrow P(n+1).$$

Kontrolli lõpus kolme asja: kas baassamm on olemas, kas induktsioonieeldus on selgelt öeldud ja kas $P(n+1)$ tõestamisel seda eeldust kasutati.

Kui mõni neist puudub, ei ole väidete ahel veel katkematu.

Näide

Väide:

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

Baassamm $n=1$:

$$1=\frac{1\cdot2}{2}.$$

Baassamm kehtib.

Induktsioonieeldus: oletame, et mingi naturaalarvu $n$ korral kehtib

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

Tahame tõestada, et siis kehtib väide ka $n+1$ korral:

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

Alustame vasakust poolest ja kasutame induktsioonieeldust:

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

Viime ühise nimetaja alla:

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

Võtame $(n+1)$ sulgude ette:

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

See on täpselt see, mida pidime tõestama. Seega kehtib valem kõigi naturaalarvude $n$ korral.

Tõlgendus: baassamm alustab ahela ja induktsioonisamm kannab tõestuse igalt $n$-lt järgmisele.

Veel üks lihtne näide

Tõesta, et

$$2+4+6+\cdots+2n=n(n+1).$$

Baassamm $n=1$:

$$2=1\cdot2.$$

Induktsioonieeldus:

$$2+4+\cdots+2n=n(n+1).$$

Lisame järgmise liikme $2(n+1)$:

$$2+4+\cdots+2n+2(n+1)=n(n+1)+2(n+1).$$

Võtame $(n+1)$ ette:

$$(n+1)(n+2).$$

See on sama valem $n+1$ jaoks:

$$(n+1)((n+1)+1).$$

Tõlgendus: baassamm ja induktsioonisamm koos näitavad, et valem kehtib kõigi naturaalarvude $n$ korral.

Tüüpviga

Induktsioon ei ole “kontrollin mõne näite peal”. Näited aitavad aimata, aga tõestuseks on vaja üldist sammu.

Teine tüüpviga on unustada baassamm. Ilma esimese doomino kukkumiseta ei piisa teadmisest, et iga doomino lükkaks järgmise.

Kolmas tüüpviga on induktsioonisammus induktsioonieeldust mitte kasutada. Kui väide tuleb tõestada $n+1$ jaoks, peab kuskil ilmuma eeldus $n$ kohta.

Neljas tüüpviga on tõestada ainult üleminekut, aga mitte öelda, millisest väärtusest tõestus algab. Kui väide algab näiteks $n=0$ korral, peab ka baassamm olema $n=0$.

Teine seletusviis

Induktsiooni võib mõelda redelina: esimene aste peab kandma ja iga astme pealt peab saama järgmisele.

Harjutused

Lihtne kontroll

1. Kontrolli summavalemit $n=3$ korral.
2. Miks on baassamm vajalik?
3. Mida tähendab induktsioonieeldus?

Rakendus

1. Tõesta induktsiooniga, et $1+3+5+\cdots+(2n-1)=n^2$.
2. Mis on induktsioonisammus vaja tõestada, kui väide on $P(n)$?

Mõtlemisülesanne

1. Miks ei piisa induktsioonitõestuses ainult juhtude $n=1,2,3$ kontrollimisest?
2. Väide $P(n)$ algab väärtusest $n=0$. Milline peab olema baassamm ja milline induktsioonisamm?
3. Õpilane kontrollib $P(1)$, eeldab $P(n)$ ja kirjutab kohe „järelikult $P(n+1)$”. Mis on tõestusest puudu?

Vastused

1. $1+2+3=6$ ja $\frac{3\cdot4}{2}=6$.
2. See käivitab tõestuse, nagu esimene doomino.
3. Oletame, et väide kehtib mingi $n$ korral, et selle abil tõestada järgmine juht.
4. Baassamm: $1=1^2$. Eeldus: $1+3+\cdots+(2n-1)=n^2$. Lisame järgmise paaritu arvu $2n+1$: $n^2+2n+1=(n+1)^2$. Seega kehtib väide kõigi naturaalarvude $n$ korral.
5. Tuleb tõestada, et $P(n)\Rightarrow P(n+1)$.
6. Sest üksikud näited ei tõesta väidet kõigi naturaalarvude kohta; vaja on ka üleminekusammu $P(n)\Rightarrow P(n+1)$.
7. Baassamm on $P(0)$. Induktsioonisammus eeldatakse $P(n)$ ja tõestatakse $P(n+1)$.
8. Puudu on põhjendus, kuidas $P(n)$ abil saadakse $P(n+1)$; eeldus üksi järgmist juhtu ei tõesta.

Seosed

Induktsioon toetub loogilisele järeldusele ja on lähedane rekursioonile: rekursioon arvutab järgmise väärtuse varasemate põhjal, induktsioon tõestab järgmise juhu varasema põhjal. Järgmine peatükk kasutab sama mõtet algoritmide ja rekursiivsete kirjelduste juures.