Publisert av Sjefen

Induksjonsbevis

Et induksjonsbevis brukes typisk i forbindelse med påstander om heltall, og går i to trinn. Vi tar utgangspunkt i en påstand, U(n), som gjelder for alle n ≥ n0. 

I trinn 1 etablerer vi induksjonsgrunnlaget, det vil si at vi fastslår at U(n) er sann for startverdien n0. 

Trinn 2 kalles induksjonstrinnet, her viser vi at hvis U(n) er sann, er U(n+1) sann. 

Av trinn 2 følger da videre at hvis U(n+1) er sann, er U((n+1)+1) = U(n+2) sann, hvis U(n+2) er sann, er U((n+2)+1) = U(n+3) sann, og så videre. Denne logikken kan vi følge videre mot uendelig, og påstanden er derfor bevist for alle n ≥ n0. 

Eksempel 1:

Vi skal bevise at summen av alle hele tall fra og med 1 til og med n er lik $\frac{\displaystyle n(n + 1)}{\displaystyle 2}$.

For eksempel er $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = \frac{\displaystyle 10(10 + 1)}{\displaystyle 2} = 55$

I trinn 1 viser vi da at påstanden er riktig for n0 = 1, det vil si at summen av tallene fra og med 1 til og med 1 er 1. Og formelen gir $\frac{\displaystyle 1(1 + 1)}{\displaystyle 2} = 1$, så påstanden er riktig for n0 = 1.

Formelen vi skal bevise sier at hvis

$1 + 2 + 3 + \cdots + {\color{brown}n} = \frac{\displaystyle {\color{brown}n}({\color{brown}n} + 1)}{\displaystyle 2}$

er

$1 + 2 + 3 + \cdots + n + ({\color{brown}{n + 1}}) = \frac{\displaystyle {(\color{brown}{n + 1}})\big(({\color{brown}{n + 1}}) + 1\big)}{\displaystyle 2}$

(For å tydeliggjøre har vi markert siste ledd i rekka med brunt.)

Regner vi ut telleren i brøken, ser vi at den blir

$\frac{\displaystyle (n + 1)(n + 2)}{\displaystyle 2}$

I trinn 2 skal vi vise at dette er riktig. Vi har altså

$1 + 2 + 3 + \cdots + n = \frac{\displaystyle n(n + 1)}{\displaystyle 2}$

Vi adderer et nytt ledd på begge sider av likhetstegnet:

$1 + 2 + 3 + \cdots + n + (n + 1) = \frac{\displaystyle n(n + 1)}{\displaystyle 2} + (n + 1)$

Vi skriver uttrykket på høyre side som en enkelt brøk:

$\frac{\displaystyle n(n + 1) + 2(n + 1)}{\displaystyle 2}$

Vi regner ut parenteser og trekker sammen like ledd:

$\frac{\displaystyle n^2 + 3n + 2}{\displaystyle 2}$

Til slutt faktoriserer vi andregradsuttrykket:

$\frac{\displaystyle(n + 1)(n + 2)}{\displaystyle 2}$

Som er det uttrykket formelen sa vi skulle få. Når formelen er gyldig for n, er den altså gyldig for n + 1. Siden vi i trinn 1 viste at formelen var gyldig for n = 1, er den følgelig gyldig for n + 1 = 2, og siden den er gyldig for n = 2 er den gyldig for n = 2 + 1 = 3, og så videre mot uendelig.

Oppgave 1:

Bevis at

$1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{\displaystyle n(n + 1)(2n+1)}{\displaystyle 6}$

for alle n ≥ 1.

Se løsningsforslag

Kilder