Eksempel 2

Oppgave 1

La $P_n$ være en påstand som avhenger av et naturlig tall $n$. Anta at vi kan vise at:

1. $P_i$ er sann, hvor $i$ er et naturlig tall.
2. Dersom det finnes et naturlig tall $k$ slik at $P_k$ er sann, så er $P_{k+1}$ også sann.

Forklar hvorfor vi med dette ikke kan påstå at $P_n$ er sann for $n < i$.

Løsning

Dersom vi klarer å vise påstand 2, har vi vist at dersom vi klarer å finne en $n$ hvor påstanden gjelder, så gjelder den også for den neste. I første påstand viser vi at at $P_n$ gjelder for $n=i$. Påstand 2 sier da at den også gjelder for den neste, altså $i+1$. Når vi har $i+1$, sier påstand 2 at den også gjelder for den neste, altså $i+2$. Og slik kan vi fortsette. La oss si at $i=3$. Da har vi bevist at påstanden $P_n$ gjelder for $n=3,4,5,6,7,...$. Problemet er at påstand 2 kun gir oss det neste leddet, men ikke tidligere ledd. Altså beviser vi at påstanden gjelder for $n=3$, vil påstand 2 gjøre at den også gjelder for alle ledd større enn 3. Men vi har ingen steder i induksjonsbeviset hvor det står at påstanden gjelder for $n< i$, her for $n=1$ og $n=2$.

Merk at dette betyr ikke at påstanden ikke gjelder for $n < i$, men vi kan ikke påstå at vi har bevist det utifra induksjonsmetoden. Dersom vi er interesserte i $n < i$, må vi velge $i$ til å være den laveste $n$'en vi er interesserte i. Påstand 2 i induksjonsbeviset gir oss da at $P_n$ gjelder for alle ledd høyere enn $i$.