Oppgaver og aktiviteter

Induksjonsbevis

Her kan du jobbe med induksjonsbevis.

1.3.10

Bruk induksjon til å vise at summen, $S_{n}$ , av de $n$ første oddetallene er

$S_{n} = 1 + 3 + 5 + . . . + (2 n - 1) = n^{2}$

Løsning

$P (n) : S_{n} = n^{2}$

$a_{n} = 2 n - 1$

Trinn 1

VS:

$S_{1} = a_{1} = 1$

HS:

$1^{2} = 1$

$P (1)$ er sann.

Trinn 2

Vi antar $P (k) : S_{k} = k^{2}$ .

Vi undersøker om $P (k) \Rightarrow P (k + 1)$ :

$\begin{array}{rcl} P (k + 1) : S_{k + 1} & = & {(k + 1)}^{2} \\ S_{k} + a_{k + 1} & = & {(k + 1)}^{2} \end{array}$

VS:

$\begin{array}{rcl} S_{k} + a_{k + 1} & = & k^{2} + 2 (k + 1) - 1 \\ = & k^{2} + 2 k + 2 - 1 \\ = & k^{2} + 2 k + 1 \end{array}$

HS:

${(k + 1)}^{2} = k^{2} + 2 k + 1$

Vi har nå vist at $P (k) \Rightarrow P (k + 1)$ .

Konklusjon

Vi har vist ved induksjon at $P (n)$ er sann for alle $n \geq 1$ .

1.3.11

Vi har gitt ei geometrisk rekke der $a_{1} = 1$ og $k = 2$ .

Vis ved induksjon at $S_{n} = 2^{n} - 1$ .

Løsning

Trinn 1

$\begin{array}{rcl} n & = & 1 : \\ VS & = & 1 \\ HS & = & 2^{1} - 1 = 1 \end{array}$

Påstanden holder for $n = 1$

Trinn 2

Vi antar at $S_{k} = 2^{k} - 1$ .

Vi har at

$\begin{array}{rcl} a_{n} & = & a_{1} \cdot k^{n - 1} \\ = & 1 \cdot 2^{n - 1} \\ = & 2^{n - 1} \\ ⇓ \\ a_{k + 1} & = & 2^{k + 1 - 1} \\ = & 2^{k} \end{array}$

Da skal vi ha at

$\begin{array}{rcl} S_{k + 1} & = & 2^{k + 1} - 1 \\ S_{k} + a_{k + 1} & = & 2^{k + 1} - 1 \end{array}$
$\begin{array}{rcl} VS & = & S_{k} + a_{k + 1} \\ = & 2^{k} - 1 + 2^{k} \\ = & 2 \cdot 2^{k} - 1 \\ = & 2^{1} \cdot 2^{k} - 1 \\ = & 2^{k + 1} - 1 \\ = & HS \end{array}$

Konklusjon

Vi har bevist ved induksjon at $S_{n} = 2^{n} - 1$ for alle $n \geq 1$ .

1.3.12

Vis ved induksjon at summen $S_{n}$ av ei aritmetisk rekke er $n \cdot \frac{a_{1} + a_{n}}{2}$ .

Løsning

Vi har at $a_{n} = a_{1} + d (n - 1)$ .

Dette gir at påstanden vi skal vise, er

$\begin{array}{rcl} P (n) : S_{n} & = & n \cdot \frac{a_{1} + a_{n}}{2} \end{array}$

Trinn 1

VS:

$S_{1} = a_{1}$

HS:

$\begin{array}{rcl} S_{1} & = & 1 \cdot \frac{a_{1} + a_{1}}{2} \\ = & \frac{2 a_{1}}{2} \\ = & a_{1} \end{array}$

Vi ser at $P (1)$ holder.

Trinn 2

Vi antar $P (k) : S_{k} = k \cdot \frac{a_{1} + a_{k}}{2}$ .

Da må vi vise

$P (k + 1) : S_{k + 1} = (k + 1) \cdot \frac{a_{1} + a_{k + 1}}{2}$

VS:

Vi har at $a_{k + 1} = a_{1} + d (k + 1 - 1) = a_{1} + d k$ .

$\begin{array}{rcl} S_{k + 1} & = & S_{k} + a_{k + 1} \\ = & S_{k} + a_{1} + d k \end{array}$

HS:

Vi har også at $a_{k + 1} = a_{k} + d$ .

$\begin{array}{rcl} (k + 1) \cdot \frac{a_{1} + a_{k + 1}}{2} & = & k \cdot \frac{a_{1} + a_{k + 1}}{2} + \frac{a_{1} + a_{k + 1}}{2} \\ = & k \cdot \frac{a_{1} + a_{k} + d}{2} + \frac{a_{1} + a_{1} + d k}{2} \\ = & k \cdot \frac{a_{1} + a_{k}}{2} + \frac{k d}{2} + \frac{2 a_{1}}{2} + \frac{d k}{2} \\ = & S_{k} + a_{1} + d k \end{array}$

De to sidene er like, og det betyr at $P (k) \Rightarrow P (k + 1)$ .

Konklusjon

Vi har nå bevist $P (n)$ for alle $n \geq 1$ ved induksjon.

1.3.13

Vis ved induksjon at summen, $S_{n}$ , av ei geometrisk rekke er $a_{1} \cdot \frac{k^{n} - 1}{k - 1}$ .

Løsning

Vi har at $a_{n} = a_{1} \cdot k^{n - 1}$ .

$P (n) : S_{n} = a_{1} \cdot \frac{k^{n} - 1}{k - 1}$

Trinn 1

VS:

$S_{1} = a_{1}$

HS:

$\begin{array}{rcl} S_{1} & = & a_{1} \cdot \frac{k^{1} - 1}{k - 1} \\ = & a_{1} \cdot \frac{k - 1}{k - 1} \\ = & a_{1} \cdot 1 \\ = & a_{1} \end{array}$

$P (1)$ er sann.

Trinn 2

Vi antar $P (r)$ . Vi undersøker om $P (r) \Rightarrow P (r + 1)$ :

(Legg merke til at vi her bruker $r$ i stedet for $k$ i trinn 2 for å unngå å blande med konstanten $k$ i den geometriske rekka.)

Vi har da

$P (r + 1) : S_{r + 1} = a_{1} \cdot \frac{k^{r + 1} - 1}{k - 1}$

$a_{r + 1} = a_{1} \cdot k^{r - 1 + 1} = a_{1} \cdot k^{r}$

Utregning:

$\begin{array}{rcl} VS & = & S_{r + 1} \\ = & S_{r} + a_{r + 1} \\ = & a_{1} \cdot \frac{k^{r} - 1}{k - 1} + a_{1} \cdot k^{r} \\ = & a_{1} (\frac{k^{r} - 1}{k - 1} + k^{r}) \\ = & a_{1} (\frac{k^{r} - 1}{k - 1} + \frac{k^{r} (k - 1)}{k - 1}) \\ = & a_{1} (\frac{k^{r} - 1 + k^{r + 1} - k^{r}}{k - 1}) \\ = & a_{1} (\frac{k^{r + 1} - 1}{k - 1}) \\ = & HS \end{array}$

Da har vi bevist at $P (r) \Rightarrow P (r + 1)$ .

Konklusjon

Siden både trinn 1 og trinn 2 er oppfylt, har vi bevist at $P (n)$ holder for alle $n$ .

1.3.14

Finn en formel for summen av de $n$ første partallene, og bevis ved induksjon at formelen er riktig.

Løsning

Vi finner først formelen.

Vi kan se på summen av partallene som ei aritmetisk rekke der

$a_{1} = 2$

$\begin{array}{rcl} a_{n} & = & a_{1} + d (n - 1) \\ = & 2 + 2 (n - 1) \\ = & 2 + 2 n - 2 \\ = & 2 n \end{array}$

Vi bruker formelen for sum av aritmetisk rekke:

$\begin{array}{rcl} S_{n} & = & n \cdot \frac{a_{1} + a_{n}}{2} \\ = & n \cdot \frac{2 + 2 n}{2} \\ = & n \cdot (1 + n) \\ = & n^{2} + n \end{array}$

Induksjonsbeviset:

Vi skal bevise påstanden

$P (n) : S_{n} = n^{2} + n$

Trinn 1

$n = 1$

VS:

$S_{1} = a_{1} = 2$

HS:

$\begin{array}{rcl} S_{1} & = & 1^{2} + 1 = 2 \end{array}$

$P (1)$ holder.

Trinn 2

Vi antar $P (k)$ og undersøker $P (k + 1)$ .

$P (k + 1) : 2 + 4 + . . . + 2 k + 2 (k + 1) = {(k + 1)}^{2} + (k + 1)$

$\begin{array}{rcl} VS & = & 2 + 4 + . . . 2 k + 2 (k + 1) \\ = & k^{2} + k + 2 k + 2 \\ = & k^{2} + 3 k + 2 \\ HS & = & {(k + 1)}^{2} + (k + 1) \\ = & k^{2} + 2 k + 1 + k + 1 \\ = & k^{2} + 3 k + 2 \end{array}$

Vi ser at $P (k) \Rightarrow P (k + 1)$ .

Konklusjon

Vi har bevist ved induksjon at summen av de $n$ første partallene er gitt ved formelen $S_{n} = n^{2} + n$ .

CC BY-SASkrevet av Tove Annette Holter, Olav Kristensen og Stein Aanensen.

Sist faglig oppdatert 31.03.2022

Induksjonsbevis

1.3.10

Trinn 1

Trinn 2

Konklusjon

1.3.11

Trinn 1

Trinn 2

Konklusjon

1.3.12

Trinn 1

Trinn 2

Konklusjon

1.3.13

Trinn 1

Trinn 2

Konklusjon

1.3.14

Trinn 1

Trinn 2

Konklusjon

Sitere eller gjenbruke?