Et induksjonsbevis er en type bevis der du prøver å si noe generelt ut ifra en mindre sammenheng. Når du utfører et induksjonsbevis, starter du med å anta at noe stemmer for en gitt verdi. Deretter ønsker du å vise at hvis det gjelder for en verdi, så må den også gjelde for den neste. Hvis dette er sant for en vilkårlig verdi, så må det gjelde generelt.

Når du skal utføre et induksjonsbevis er følgende oppskrift med tre steg svært nyttig!

Regel

Framgangsmåte ved induksjonsbevis

1.: Sjekk at det stemmer for første verdien av $n$ .
2.: Anta at det stemmer for $n = k$ , slik at $\dots$
3.: Du må da vise at det stemmer for $n = k + 1$ , slik at $\dots$

NB! Nøkkelen til induksjonsbevis er å smugle antagelsen fra Punkt 2 inn i Punkt 3. Dette er den kritiske brikken i beviset!

Eksempel 1

Induksjon på rekker

Vis at $1 + 3 + 5 + \dots + (2 n - 1) = n^{2}$

1.: Sjekk at det stemmer for første verdien av $n$ ved å sette inn i uttrykket $2 n - 1$ : $\begin{array}{l} 1 & = 1^{2} & ✓ \end{array}$
2.: Anta at det stemmer for $n = k$ , slik at (bruker nå uttrykket i oppgaven direkte, men bytter $n$ med $k$ )

1 + 3 + 5 + \dots + (2 k - 1) = k^{2}

(1)

3.: Du må da vise at det stemmer for $n = k + 1$ , slik at (bruker nå uttrykket i oppgaven direkte, men bytter $n$ med $k + 1$ . Husk parenteser!)

1 + \dots + (2 k - 1) + (2 (k + 1) - 1) = {(k + 1)}^{2}

(2)

1 + 3 + \dots + (2 k - 1) + (2 (k + 1) - 1) = {(k + 1)}^{2}

(3)

4.

Du begynner nå utregningsdelen av beviset ditt. Den skal begynne med venstresiden i (3), og fortsette med at antagelsen (1) smugles inn. Se nøye på det som skjer under! Til slutt skal du ende med det som står på høyresiden av likheten i (3).

Du må nå bruke antagelsen for å skrive et pent uttrykk for de første $k$ leddene:

\begin{array}{l} \underset{Sett inn uttrykket fra (1)}{\underset{⏟}{1 + 3 + 5 + \dots + (2 k - 1)}} + (2 (k + 1) - 1) \\ = k^{2} + (2 (k + 1) - 1) \\ = k^{2} + 2 k + 1 \\ = {(k + 1)}^{2} . \end{array}

\begin{array}{l} \underset{Sett inn uttrykket fra (1)}{\underset{⏟}{1 + 3 + 5 + \dots + (2 k - 1)}} + (2 (k + 1) - 1) & = k^{2} + (2 (k + 1) - 1) \\ = k^{2} + 2 k + 1 \\ = {(k + 1)}^{2} . \end{array}

Q.E.D

Eksempel 2

Induksjon på delelighet

Vis at $n^{2} - n$ er delelig med 2

Hvis noe er delelig med 2, må det ha 2 som faktor. Det må altså kunne skrives som $n^{2} - n = 2 t$ , der $t$ er et helt tall.

1.: Sjekk at det stemmer for første verdien av $n$ ved å sette inn i uttrykket $n^{2} - n$ : $\begin{array}{l} 1^{2} - 1 = 0 & = 2 \cdot 0 & ✓ \end{array}$
2.: Antar at det stemmer for $n = k$ , slik at (bruker nå uttrykket i oppgaven direkte, men bytter $n$ med $k$ )

k^{2} - k = 2 u

(4)

3.: Du må da vise at det stemmer for $n = k + 1$ , slik at (bruker nå uttrykket i oppgaven direkte, men bytter $n$ med $k + 1$ . Husk parenteser!)

(5)

4.

Du begynner nå utregningsdelen av beviset ditt. Den skal begynne med venstresiden i (5), og fortsette med at antagelsen (4) smugles inn. Se nøye på det som skjer under! Til slutt skal du ende med det som står på høyresiden av likheten i (5).

Du må nå bruke antagelsen og da vil $n = k + 1$ gi følgende:

\begin{array}{l} {(k + 1)}^{2} - (k + 1) & = \underset{Stokker om for å bruke (4)}{\underset{⏟}{k^{2} + 2 k + 1 - k - 1}} \\ = \underset{Bruker (4)}{\underset{⏟}{k^{2} - k}} + 2 k \\ = 2 u + 2 k \\ = 2 (u + k) \\ = 2 t, der t = u + k . \end{array}

Q.E.D

Eksempel 3

Induksjon på derivasjon

La $f (x) = e^{2 x}$ . Vis at $f^{(n)} = 2^{n} e^{2 x}$ .

Her betyr altså $f^{(n)}$ at $f$ blir derivert $n$ ganger.

1.: Sjekk at det stemmer for første verdien av $n$ ved å sette inn i uttrykket $f^{(n)} = 2^{n} e^{2 x}$ : $\begin{array}{l} f^{(1)} (x) = 2 e^{2 x} & = 2^{1} e^{2 x} & ✓ \end{array}$
2.: Antar at det stemmer for $n = k$ , slik at (bruker nå uttrykket i oppgaven direkte, men bytter $n$ med $k$ )

f^{(k)} (x) = 2^{k} e^{2 x}

(6)

3.: Må nå vise at det stemmer for $n = k + 1$ , slik at (bruker nå uttrykket i oppgaven direkte, men bytter $n$ med $k + 1$ . Husk parenteser!)

f^{(k + 1)} (x) = 2^{k + 1} e^{2 x}

(7)

4.

Du begynner nå utregningsdelen av beviset ditt. Den skal begynne med venstresiden i (7), og fortsette med at antagelsen (6) smugles inn. Se nøye på det som skjer under! Til slutt skal du ende med det som står på høyresiden av likheten i (7).

Du må nå bruke antagelsen ved å skrive $f^{(k + 1)} (x)$ som ${(f^{(k)} (x))}^{'}$ :

\begin{array}{l} f^{(k + 1)} (x) & = \underset{Sett inn (6)}{\underset{⏟}{{(f^{(k)} (x))}^{'}}} \\ = {(2^{k} e^{2 x})}^{'} \\ = 2 \cdot 2^{k} e^{2 x} \\ = 2^{k + 1} e^{2 x} . \end{array}

Q.E.D