Formler, teknikker og begreper du trenger til eksamen.
KompetansemålInduksjon beviser at en påstand gjelder for alle naturlige tall via to trinn: basissteg og induksjonssteg.
Oppbygging av beviset
Et induksjonsbevis har to trinn.
Basissteg: Vis at er sant (noen ganger ).
Induksjonssteg: Anta at er sant for et vilkårlig . Denne antakelsen kalles induksjonshypotesen. Vis deretter at følger.
Når begge trinnene er vist, gjelder påstanden for alle naturlige tall.
Basissteg: Vis at er sant (noen ganger ).
Induksjonssteg: Anta at er sant for et vilkårlig . Denne antakelsen kalles induksjonshypotesen. Vis deretter at følger.
Når begge trinnene er vist, gjelder påstanden for alle naturlige tall.
Gjennomarbeidet eksempel: sumformel
Vis at for alle .
Basis: : Venstre side er 1. Høyre side er . Stemmer.
Induksjonssteg: Anta formelen gjelder for . Legg til :
Dette er nettopp formelen for . Bevist.
Basis: : Venstre side er 1. Høyre side er . Stemmer.
Induksjonssteg: Anta formelen gjelder for . Legg til :
Dette er nettopp formelen for . Bevist.
Induksjon for delelighet
Vis at for alle .
Basis: , som er delelig med 3.
Induksjonssteg: Anta . Da er .
Første ledd er delelig med 3 etter induksjonshypotesen, og 3 er delelig med 3. Dermed er summen delelig med 3.
Basis: , som er delelig med 3.
Induksjonssteg: Anta . Da er .
Første ledd er delelig med 3 etter induksjonshypotesen, og 3 er delelig med 3. Dermed er summen delelig med 3.
Vanlige feil
Skriv alltid ned induksjonshypotesen eksplisitt. Pek tydelig ut stedet der du bruker den i induksjonstrinnet. Glemmer du det, er beviset ufullstendig. Husk at basis kan starte ved et annet tall enn 1.
Eksempel