Induksjonssteget er å vise at hvis påstanden holder for et vilkårlig naturlig tall $n$, så holder den også for $n + 1$.
Definisjon: Matematisk induksjon
Test deg selv
Tidligere formulerte vi påstanden om at for alle naturlige tall $n$ er summen av de $n$ første oddetallene lik $n^2$. Hvis vi skal bevise denne påstanden ved matematisk induksjon, hva vil være induksjonssteget i beviset?
Dette vil være basissteget i beviset, ikke induksjonssteget.
Dette er påstanden vi faktisk skal bevise i induksjonsbeviset.
Utfordring
La oss tenke oss at vi klarer å bevise de to punktene fra forrige Test deg selv-oppgave:
IN1150-studenten som står lengst til venstre har superkrefter.
Hvis en vilkårlig IN1150-student i rekken har superkrefter, så har den neste studenten til høyre superkrefter.
Et bevis for punkt 1 ville vært basissteget og et bevis for punkt 2 vært
induksjonssteget i et induksjonsbevis for at alle studentene i rekken har
superkrefter.
Hva ville vært induksjonshypotesen i dette beviset?
Dette er det vi viser i induksjonssteget i beviset. I induksjonssteget antar vi at en vilkårlig student i rekken har superkrefter, og viser at da må den neste studenten til høyre ha superkrefter. Det er denne antagelsen om at en vilkårlig student har superkrefter som kalles for induksjonshypotsen. Induksjonshypotesen er altså en antagelse vi gjør som en del av induksjonssteget i beviset.
Induksjonshypotsen her er at en vilkårlig student i rekken har superkrefter. I induksjonssteget jobber vi ut fra denne hypotesen, og viser at under denne hypotesen har også den neste studenten til høyre superkrefter.
Utfordring
La oss igjen se på påstanden om at summen av de $n$ første oddetallene er lik $n^2$. Vi kan bevise dette ved å vise at det første oddetallet, $1$, er lik $1^2$ (basissteget), og at hvis summen av de $n$ første oddetallene er lik $n^2$ der $n$ er et vilkårlig naturlige tall, så er summen av de $n + 1$ første oddetallene lik $(n+1)^2$ (induksjonssteget).
Hva ville vært induksjonshypotesen i et slikt bevis?
Dette er ikke induksjonshypotesen, men kun en påstand om tallet $1$.
Dette er ikke induksjonshypotesen, men det vi viser i induksjonssteget. I induksjonssteget antar vi at at påstanden er sann for et vilkårlig naturlig tall $n$, og viser at påstanden da også må være sann for $n+1$. Det er denne antagelsen om at påstanden er sann for et vilkårlig tall $n$ som kalles for induksjonshypotsen. Induksjonshypotesen er altså en antagelse vi gjør som en del av induksjonssteget i beviset.
Induksjonshypotesen er at påstanden er sann for et vilkårlig tall $n$, altså at summen av de $n$ første oddetallene er lik $n^2$ for et vilkårlig tall $n$. I induksjonssteget jobber vi ut fra denne hypotesen, og viser at under denne hypotesen er summen av de $n+1$ første oddetallene lik $(n+1)^2$.