Hopp til innhold

  1. Home
  2. Matematikk for realfagChevronRight
  3. AlgebraChevronRight
  4. InduksjonsbevisChevronRight
  5. InduksjonsbevisChevronRight
SubjectMaterialFagstoff

Fagartikkel

Induksjonsbevis

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.

Læringsressurser

Induksjonsbevis

SubjectEmne

Fagstoff

SubjectEmne

Oppgaver og aktiviteter