Njuike sisdollui
Fágaartihkal

Induksjonsbevis

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 n 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:

  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(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:

HS = 2(k+1)2= 2(k2+2k+1)= 2k2+4k+2VS = 2k2+4(k+1)-2= 2k2+4k+4-2= 2k2+4k+2

Vi har nå vist at dersom påstanden stemmer for n=k, må den også stemme for n=k+1. Matematisk skriver vi at PkPk+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 n1.

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=2 og an+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 PkPk+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 n1.

Filmer om induksjonsbevis

Video: Tom Jarle Christiansen / CC BY-SA 4.0
Video: Tom Jarle Christiansen / CC BY-SA 4.0
CC BY-SA 4.0Dán lea/leat čállán Tove Annette Holter, Olav Kristensen ja Stein Aanensen.
Maŋemusat ođastuvvon 2022-05-24