Fagstoff

Induksjonsbevis

Publisert: 04.03.2013, Oppdatert: 05.03.2017
  • Innbygg
  • Enkel visning
  • Lytt til tekst
  • Skriv ut

  Når vi har arbeidet med tallfølger og tallrekker, har du sett mange formler som inneholder variabelen n, der n står for et naturlig tall større enn eller lik 1. For eksempel har du sett 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.

Induksjonsaksiomet

Vi ønsker å bevise at en setning som omhandler et naturlig tall n, gjelder for alle naturlige tall. Et induksjonsbevis foregår over to trinn.

 

Trinn 1

Vi viser at formelen gjelder for n = 1.

Dette kalles induksjonsgrunnlaget.

 

Trinn 2

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

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

Dette kalles induksjonstrinnet.

 

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

 

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

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

Eksempel 1

 

Vi vil bruke induksjon til å vise at summen av 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

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-1=2t+1-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.

Induksjonsbevis eksempel 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

Induksjonsbevis eksempel 2  

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

Oppgaver

Generelt