Her skal du lære en bevistype som egner seg godt ved arbeid med rekker.
Når vi jobber med matematiske rekker, har vi ofte en formel for for eksempel summen av de første leddene i rekka eller en eksplisitt formel for an.
Induksjonsbevis
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:
Trinn 1: Vi viser at påstanden gjelder for en bestemt verdi av n, som oftest n=1. Dette trinnet kalles ofte induksjonsgrunnlaget.
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.
Konklusjon
Vi skal vise hvordan induksjonsbevis gjennomføres ved hjelp av et eksempel.
Vi skal bevise følgende påstand:
P(n):2+6+10+...+4n-2=2n2
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:
VS=2HS=2·12=2
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 Pk, det vil si at vi går ut fra at
2+6+10+...+4k-2=2k2
Dette betyr at vi må undersøke om
2+6+10+...+4k-2+4k+1-2=2k+12
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:
2k2+4k+1-2=2k+12
Vi undersøker om venstre side og høyre side er like:
Vi har nå vist at dersom påstanden stemmer for n=k, må den også stemme for n=k+1. Matematisk skriver vi at Pk⇒Pk+1.
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≥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.
Eksempel
Ei rekke er gitt ved
a1=2ogan+1=an+n+2
Vi skal bruke induksjon til å vise at ledd nummer n kan skrives som
Pn:an=nn+32
Trinn 1
VS=a1=2HS=1(1+3)2=2
Vi ser at P1 holder.
Trinn 2
Vi antar at Pk holder, det vil si at ak=kk+32.
Vi undersøker om Pk⇒Pk+1:
Pk+1:ak+k+2=k+1k+1+32kk+32+k+2=k+1k+42
Vi sjekker om venstre side er lik høyre side:
VS=kk+32+k+2=kk+32+2k+22=k2+3k+2k+42=k2+5k+42
HS=k+1k+42=k2+4k+k+42=k2+5k+42
Vi ser at P(k+1) holder dersom Pk holder.
Konklusjon
Vi har nå bevist ved induksjon at Pn er sann for alle n≥1.