Matemaattinen induktio

Matemaattinen induktio on matemaattinen todistus, joka kuuluu matemaattisen algebran päähaaraan.

Matemaattinen induktio perustuu induktioperiaatteeseen, jolla todistetaan luonnollista lukua $n$ koskeva väite todeksi kaikilla $n$:n arvoilla, esim. $1+2+3+...+n=n(n+1)/2$. Tämä perustuu siihen, että jos joukolle A pätee

1) $0\in A$ ja

2) Ehdosta $n\in A\Rightarrow n+1\in A$,

niin $A=\mathbb {N}$.

Matemaattinen induktio koostuu kolmesta vaiheesta:

1. Perusaskel

Osoitetaan, että $P(0)$ on tosi

2. Induktioaskel

Induktio-oletus: $P(n)$ on tosi arvolla $n=k$

Induktioväite: $P(n)$ tosi arvolla $n=k+1$

Todistus: todistetaan, että oletuksesta seuraa väitös

3. Johtopäätös

Induktioaskeleessa todistettiin, että $P(n)$ on tosi aina seuraavalla $n$:n arvolla. Tämän induktioperiaatteen mukaan $P(n)$ on tosi kaikilla $n$:n luonnollisilla arvoilla.