Fagstoff

Induksjonsbevis

Publisert: 04.03.2013, Oppdatert: 31.10.2018

Ved induksjonsbevis kan vi effektivt bevise påstander som gjelder for naturlige tall.

  Når vi arbeider med tallfølger og tallrekker, er det mange formler som inneholder variabelen n, der n står for et naturlig tall større enn eller lik 1. For eksempel har vi flere eksplisitte formler for ledd nummer n i en tallfølge.

Matematikerne har kommet fram til mange av disse formlene ved å føre en type bevis som vi kaller induksjonsbevis. Denne bevistypen bygger på induksjonsaksiomet. Et aksiom er en grunnleggende setning som er selvinnlysende og godtas uten bevis.

Vi ønsker å bevise at en påstand gjelder for alle naturlige tall.

 

Induksjonsaksiomet

Et induksjonsbevis foregår over to trinn.

 

Trinn 1

Vi viser at påstanden gjelder for  n=1.

Dette kalles induksjonsgrunnlaget.

 

Trinn 2

Vi antar at påstanden gjelder for et vilkårlig tall n=t  der t1.

Vi viser at da må påstanden også gjelde for n=t+1 .

Dette kalles induksjonstrinnet.

 

Induksjonsaksiomet sier at vi nå kan konkludere med at påstanden gjelder for alle n1.

 

Hvorfor kan vi si at påstanden nå gjelder for alle n1?

  • I trinn 2 viser vi at hvis påstanden gjelder for en verdi av n, så gjelder den også for den neste verdien av n.
  • I trinn 1 har vi vist at påstanden gjelder når  n=1. Det vi har vist i trinn 2, må bety at påstanden da også gjelder for  n=2. Men siden påstanden gjelder for  n=2 , må den også gjelde for n=3. Slik kan vi holde på i det uendelige, og påstanden må derfor gjelde for alle n1.

Eksempel 1

 

Vi vil bruke induksjon til å vise at summen av de n første leddene i en geometrisk rekke med a1=1 og k=2 kan skrives som

Sn=2n-1

Vi skal altså vise at

1+2+4+ ... +2n-1=2n-1

Trinn 1, induksjonsgrunnlaget

Vi skal vise at formelen gjelder for n=1 .

Bevis

Når n=1, har vi bare ett ledd på venstre side.

Venstre side =1

Høyre side =21-1=1

Da vet vi at formelen gjelder for n=1.

Trinn 2, Induksjonstrinnet

Vi antar at formelen gjelder for  n=t. Vi antar altså at

St=1+2+4+ ... +2t-1=2t-1

Vi må vise at formelen gjelder for  n=t+1. Vi må altså vise at

St+1=1+2+4+ ... +2t+1-1=2t+1-1

Bevis

Dette er en geometrisk rekke med  k=2.

St+1 = St+at+1=1+2+4+ ... +2t-1+2t-1·2=2t-1+2t-1+1=2t-1+2t=2·2t-1=2t+1-1

 

Vi har dermed vist at formelen gjelder for  n=t+1. I følge induksjonsprinsippet gjelder formelen da for alle verdier av n1.

Eksempel 2

En 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 an=nn+32

Trinn 1, induksjonsgrunnlaget

Vi skal vise at formelen gjelder for n=1.

Bevis

Venstre side =a1=2

Høyre side =11+32=42=2

Formelen gjelder for n=1.

Trinn 2, induksjonstrinnet

Vi antar at formelen gjelder for n=t. Det betyr at

at=tt+32

Vi må vise at formelen gjelder for n=t+1. Vi må altså vise at

at+1=t+1t+1+32=t+1t+42=t2+5t+42

Bevis

Vi vet at

an+1=an+n+2

Da må vi også ha at

at+1 = at+t+2=at+t+2=t(t+3)2+t+2=t(t+3)2+(t+2)·22=t2+3t+2t+42=t2+5t+42

Vi har dermed vist at formelen gjelder for n=t+1. I følge induksjonsprinsippet gjelder formelen da for alle verdier av n1.