Induksjonsbevis

Når vi jobbar med matematiske rekker, har vi ofte ein formel for til dømes summen av dei $$ n$$ første ledda i rekka eller ein eksplisitt formel for $$ a_n$$.

I matematikken har vi ein bevistype som høver spesielt godt til å vise at slike formlar er rette, det vi kallar induksjonsbevis. Innan logikken inneber induksjon at at vi trekker ei slutning om noko allmenngyldig ut frå enkelttilfelle. Eit matematisk induksjonsbevis har tre viktige nivå:

1. Trinn 1: Vi viser at påstanden gjeld for ein bestemd verdi av $$ n$$, som oftast $$ n=1$$. Dette trinnet blir ofte kalla induksjonsgrunnlaget.

2. Trinn 2: Vi viser at dersom påstanden gjeld for ein generell verdi $$ k$$, vil han òg gjelde for $$ k+1$$. Dette trinnet blir kalla induksjonstrinnet.

3. Konklusjon

Vi skal vise korleis induksjonsbevis blir gjennomførte ved hjelp av eit døme.

Vi skal bevise denne påstanden:

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

Trinn 1

Vi vil først vise at venstre side er lik høgre side for $$ n=1$$. Sidan dette er ei rekke, vil venstre side bli berre 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 gjer vi det vi kallar ei antaking. Vi går ut frå at påstanden vår er sann for $$ n=k$$. Dette kan vi ikkje vite om er sant, men vi skal vise at dersom det er sant, må påstanden òg vere sann for $$ n=k+1$$.

Vi går ut frå at $$ P\left(k\right)$$, det vil seie at vi går ut frå 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øgre side er den formelen vi skal bevise innsett $$ k+1$$.

Ved å bruke antakinga 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øgre 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 no vist at dersom påstanden stemmer for $$ n=k$$, må han òg stemme for $$ n=k+1$$. Matematisk skriv vi at $$ P\left(k\right)\Rightarrow P\left(k+1\right)$$.

Konklusjon

No har vi det vi treng for å konkludere med at påstanden vår held for alle $$ n$$. I trinn 1 viste vi at påstanden held for $$ n=1$$. Ved hjelp av trinn 2 veit vi no at påstanden held for $$ n=2$$ òg. Sidan påstanden held for $$ n=2$$, veit vi at han held for $$ n=3$$ òg. Slik kan vi halde fram, og dermed har vi bevist at påstanden held for alle $$ n\ge 1$$.

Tenk over

I trinn 2 viste vi at dersom påstanden held for $$ n=k$$, vil han òg halde for $$ n=k+1$$. Kvifor er ikkje dette godt nok bevis åleine?

Forklaring

Vi må hugse på at i trinn 2 gjorde vi ei antaking om at påstanden heldt for ein generell $$ k$$. Men vi kan ikkje eigentleg vite om det er sant. Til det treng vi trinn 1.

Vi kan tenke oss matematisk induksjon som eit dominospel. Det at alle brikkene fell, inneber at påstanden er sann. I trinn 2 viser vi at brikkene står nært nok kvarandre, slik at ei brikke vil rive ned den neste dersom ho fell. Men det hjelper ikkje at brikkene står nært nok dersom ikkje ei einaste brikke fell. I trinn 1 viser vi nettopp dette: Brikke nummer 1 fell, og då fell også alle dei 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 skrivast 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)$$ held.

Trinn 2

Vi går ut frå at $$ P\left(k\right)$$ held, det vil seie 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 sjekkar om venstre side er lik høgre 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)$$ held dersom $$ P\left(k\right)$$ held.

Konklusjon

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