Induksjonsbevis

Når vi jobber med matematiske rekker, har vi ofte en formel for for eksempel summen av de $$ n$$ første leddene i rekka eller en eksplisitt formel for $$ a_n$$.

I matematikken har vi en bevistype som er spesielt velegnet til å vise at slike formler er riktige, det vi kaller induksjonsbevis. Innen logikken innebærer induksjon at at vi trekker en slutning om noe allmenngyldig ut fra enkelttilfeller. Et matematisk induksjonsbevis har tre viktige nivåer:

1. Trinn 1: Vi viser at påstanden gjelder for en bestemt verdi av $$ n$$, som oftest $$ n=1$$. Dette trinnet kalles ofte induksjonsgrunnlaget.

2. Trinn 2: Vi viser at dersom påstanden gjelder for en generell verdi $$ k$$, vil den også gjelde for $$ k+1$$. Dette trinnet kalles induksjonstrinnet.

3. Konklusjon

Vi skal vise hvordan induksjonsbevis gjennomføres ved hjelp av et eksempel.

Vi skal bevise følgende påstand:

$$ P\left(n\right): 2+6+10+ ... + 4n-2=2n^2$$

Trinn 1

Vi vil først vise at venstre side er lik høyre side for $$ n=1$$. Siden dette er ei rekke, vil venstre side bli bare det første leddet:

$$ \begin{array}{rcl}VS & =& 2\\ HS & =& 2·1^2 =2\end{array}$$

Påstanden stemmer altså for $$ n=1$$.

Trinn 2

I dette trinnet gjør vi det vi kaller en antakelse. Vi antar at påstanden vår er sann for $$ n=k$$. Dette kan vi ikke vite om er sant, men vi skal vise at hvis det er sant, må også påstanden være sann for $$ n=k+1$$.

Vi antar $$ P\left(k\right)$$, det vil si at vi går ut fra at

$$ 2+6+10+ ... +4k-2 =2k^2$$

Dette betyr at vi må undersøke om

$$ $ 2+6+10+ ... +4k-2 +4\left(k+1\right)-2=2{\left(k+1\right)}^2$$$

Det siste leddet på venstre side (det blå) er ledd nummer $$ k+1$$, mens høyre side er den formelen vi skal bevise innsatt $$ k+1$$.

Ved å bruke antakelsen vår, kan vi skrive om uttrykket slik:

$$ $ $ 2k^2 +4\left(k+1\right)-2=2{\left(k+1\right)}^2$$$$

Vi undersøker om venstre side og høyre side er like:

$$ \begin{array}{rcl}HS & =& 2(k+1{)}^2\\ & =& 2(k^2+2k+1)\\ & =& 2k^2+4k+2\\ VS & =& 2k^2+4(k+1)-2\\ & =& 2k^2+4k+4-2\\ & =& 2k^2+4k+2\end{array}$$

Vi har nå vist at dersom påstanden stemmer for $$ n=k$$, må den også stemme for $$ n=k+1$$. Matematisk skriver vi at $$ P\left(k\right)\Rightarrow P\left(k+1\right)$$.

Konklusjon

Vi har nå det vi trenger for å konkludere med at påstanden vår holder for alle $$ n$$. I trinn 1 viste vi at påstanden holder for $$ n=1$$. Ved hjelp av trinn 2 vet vi nå at påstanden også holder for $$ n=2$$. Siden påstanden holder for $$ n=2$$, vet vi at den også holder for $$ n=3$$. Slik kan vi fortsette, og dermed har vi bevist at påstanden holder for alle $$ n\ge 1$$.

Tenk over

I trinn 2 viste vi at dersom påstanden holder for $$ n=k$$, vil den også holde for $$ n=k+1$$. Hvorfor er ikke dette godt nok bevis alene?

Forklaring

Vi må huske på at i trinn 2 gjorde vi en antakelse om at påstanden holdt for en generell $$ k$$. Men vi kan ikke egentlig vite om det er sant. Til det trenger vi trinn 1.

Vi kan tenke oss matematisk induksjon som et dominospill. Det at alle brikkene faller, innebærer at påstanden er sann. I trinn 2 viser vi at brikkene står nært nok hverandre, slik at en brikke vil rive ned den neste hvis den faller. Men det hjelper ikke at brikkene står nært nok hvis ikke en eneste brikke faller. I trinn 1 viser vi nettopp dette: Brikke nummer 1 faller, og da faller også alle de andre brikkene etter tur.

Ei rekke er gitt ved

$a_1=2 \mathrm{og} a_{n+1}=a_n+n+2$

Vi skal bruke induksjon til å vise at ledd nummer $n$ kan skrives som

$$ P\left(n\right): a_n=\frac{n\left(n+3\right)}{2}$$

Trinn 1

$$ \begin{array}{rcl}VS & =& a_1\\ & =& 2\\ HS & =& \frac{1(1+3)}{2}\\ & =& 2\end{array}$$

Vi ser at $$ P\left(1\right)$$ holder.

Trinn 2

Vi antar at $$ P\left(k\right)$$ holder, det vil si at $$ a_k=\frac{k\left(k+3\right)}{2}$$.

Vi undersøker om $$ P\left(k\right)\Rightarrow P\left(k+1\right)$$:

$$ \begin{array}{rcl}P\left(k+1\right):& & \\ a_k+k+2 & =& \frac{\left(k+1\right)\left(k+1+3\right)}{2}\\ \frac{k\left(k+3\right)}{2}+k+2 & =& \frac{\left(k+1\right)\left(k+4\right)}{2}\end{array}$$

Vi sjekker om venstre side er lik høyre side:

$$ \begin{array}{rcl}VS & =& \frac{k\left(k+3\right)}{2}+k+2\\ & =& \frac{k\left(k+3\right)}{2}+\frac{2\left(k+2\right)}{2}\\ & =& \frac{k^2+3k+2k+4}{2}\\ & =& \frac{k^2+5k+4}{2}\end{array}$$

$$ \begin{array}{rcl}HS & =& \frac{\left(k+1\right)\left(k+4\right)}{2}\\ & =& \frac{k^2+4k+k+4}{2}\\ & =& \frac{k^2+5k+4}{2}\end{array}$$

Vi ser at $$ P(k+1)$$ holder dersom $$ P\left(k\right)$$ holder.

Konklusjon

Vi har nå bevist ved induksjon at $$ P\left(n\right)$$ er sann for alle $$ n\ge 1$$.