House of Math-logo

Hva er et induksjonsbevis?


Et induksjonsbevis er en type bevis der du prøver å si noe generelt ut ifra en mindre sammenheng. Når du utfører et induksjonsbevis, starter du med å anta at noe stemmer for en gitt verdi. Deretter ønsker du å vise at hvis det gjelder for en verdi, så må den også gjelde for den neste. Hvis dette er sant for en vilkårlig verdi, så må det gjelde generelt.

Når du skal utføre et induksjonsbevis er følgende oppskrift med tre steg svært nyttig!

Regel

Framgangsmåte ved induksjonsbevis

1.
Sjekk at det stemmer for første verdien av n.
2.
Anta at det stemmer for n = k, slik at
3.
Du må da vise at det stemmer for n = k + 1, slik at

NB! Nøkkelen til induksjonsbevis er å smugle antagelsen fra Punkt 2 inn i Punkt 3. Dette er den kritiske brikken i beviset!

Eksempel 1

Induksjon rekker

Vis at 1 + 3 + 5 + + (2n 1) = n2

1.
Sjekk at det stemmer for første verdien av n ved å sette inn i uttrykket 2n 1: 1 = 12
2.
Anta at det stemmer for n = k, slik at (bruker nå uttrykket i oppgaven direkte, men bytter n med k)
1 + 3 + 5 + + (2k 1) = k2 (1)

3.
Du må da vise at det stemmer for n = k + 1, slik at (bruker nå uttrykket i oppgaven direkte, men bytter n med k + 1. Husk parenteser!)

1 + + (2k 1) + (2 (k + 1) 1) = (k + 1) 2 (2)

1 + 3 + + (2k 1) + (2 (k + 1) 1) = (k + 1) 2 (3)

4.
Du begynner nå utregningsdelen av beviset ditt. Den skal begynne med venstresiden i (3), og fortsette med at antagelsen (1) smugles inn. Se nøye på det som skjer under! Til slutt skal du ende med det som står på høyresiden av likheten i (3).

Du må nå bruke antagelsen for å skrive et pent uttrykk for de første k leddene:

= 1 + 3 + 5 + + (2k 1) Sett inn uttrykket fra (1) + (2 (k + 1) 1) = k2 + (2 (k + 1) 1) = k2 + 2k + 1 = (k + 1) 2.

1 + 3 + 5 + + (2k 1) Sett inn uttrykket fra (1) + (2 (k + 1) 1) = k2 + (2 (k + 1) 1) = k2 + 2k + 1 = (k + 1) 2.

Q.E.D

Eksempel 2

Induksjon delelighet

Vis at n2 n er delelig med 2

Hvis noe er delelig med 2, må det ha 2 som faktor. Det må altså kunne skrives som n2 n = 2t, der t er et helt tall.

1.
Sjekk at det stemmer for første verdien av n ved å sette inn i uttrykket n2 n: 12 1 = 0 = 2 0
2.
Antar at det stemmer for n = k, slik at (bruker nå uttrykket i oppgaven direkte, men bytter n med k)
k2 k = 2u (4)

3.
Du må da vise at det stemmer for n = k + 1, slik at (bruker nå uttrykket i oppgaven direkte, men bytter n med k + 1. Husk parenteser!)
(k + 1) 2 (k + 1) = 2t (5)

4.
Du begynner nå utregningsdelen av beviset ditt. Den skal begynne med venstresiden i (5), og fortsette med at antagelsen (4) smugles inn. Se nøye på det som skjer under! Til slutt skal du ende med det som står på høyresiden av likheten i (5).

Du må nå bruke antagelsen og da vil n = k + 1 gi følgende:

(k + 1) 2 (k + 1) = k2 + 2k + 1 k 1 Stokker om for å bruke (4) = k2 k Bruker (4) + 2k = 2u + 2k = 2 (u + k) = 2t,der t = u + k.

Q.E.D

Eksempel 3

Induksjon derivasjon

La f (x) = e2x. Vis at f (n) = 2ne2x.

Her betyr altså f (n) at f blir derivert n ganger.

1.
Sjekk at det stemmer for første verdien av n ved å sette inn i uttrykket f (n) = 2ne2x: f (1) (x) = 2e2x = 21e2x
2.
Antar at det stemmer for n = k, slik at (bruker nå uttrykket i oppgaven direkte, men bytter n med k)
f (k) (x) = 2ke2x (6)

3.
Må nå vise at det stemmer for n = k + 1, slik at (bruker nå uttrykket i oppgaven direkte, men bytter n med k + 1. Husk parenteser!)
f (k+1) (x) = 2k+1e2x (7)

4.
Du begynner nå utregningsdelen av beviset ditt. Den skal begynne med venstresiden i (7), og fortsette med at antagelsen (6) smugles inn. Se nøye på det som skjer under! Til slutt skal du ende med det som står på høyresiden av likheten i (7).

Du må nå bruke antagelsen ved å skrive f (k+1) (x) som (f (k) (x)): f (k+1) (x) = (f (k) (x)) Sett inn (6) = (2ke2x) = 2 2ke2x = 2k+1e2x.

Q.E.D

Vil du vite mer?Registrer degDet er gratis!
Pil som peker til venstreForrige oppslag
Hva er et kontrapositivt bevis?
Neste oppslagPil som peker til høyre
Hvordan bevise Pytagoras' setning