Matemaatiline induktsioon

Mõiste

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

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.

Valemid ja tingimused

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.

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

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

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.$$

Siis

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

Induktsioonieelduse abil:

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

See on sama valem $n+1$ korral, seega väide kehtib kõigi $n\in\mathbb N$ jaoks.

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.