Induksjonsbevis

$$ P\left(n\right): S_n=n^2$$

$$ a_n=2n-1$$

Trinn 1

VS:

$$ S_1 = a_1 = 1$$

HS:

$$ 1^2=1$$

$$ P\left(1\right)$$ er sann.

Trinn 2

Vi antar $$ P\left(k\right): S_k=k^2$$.

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

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

VS:

$$ \begin{array}{rcl}{S}_k+a_{k+1} & =& k^2+2\left(k+1\right)-1\\ & =& k^2+2k+2-1\\ & =& k^2+2k+1\end{array}$$

HS:

$$ {\left(k+1\right)}^2 = k^2+2k+1$$

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

Konklusjon

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

Trinn 1

$$ \begin{array}{rcl}n & =& 1:\\ \mathrm{VS} & =& 1\\ \mathrm{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·k^{n-1}\\ & =& 1·2^{n-1}\\ & =& 2^{n-1}\\ & \Downarrow & \\ 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}\mathrm{VS} & =& S_k+a_{k+1} \\ & =& 2^k-1+2^k\\ & =& 2·2^k-1\\ & =& 2^1·2^k-1\\ & =& 2^{k+1}-1 \\ & =& \mathrm{HS}\end{array}$$

Konklusjon

Vi har bevist ved induksjon at $$ S_n = 2^n-1$$ for alle $$ n\ge 1$$.

Vi har at $$ a_n = a_1+d\left(n-1\right)$$.

Dette gir at påstanden vi skal vise, er

$$ \begin{array}{rcl}P\left(n\right): S_n & =& n·\frac{a_1+a_n}{2}\end{array}$$$$ $$

Trinn 1

VS:

$$ S_1 = a_1$$

HS:

$$ \begin{array}{rcl}{S}_1 & =& 1·\frac{a_1+a_1}{2}\\ & =& \frac{2a_1}{2}\\ & =& a_1\end{array}$$

Vi ser at $$ P\left(1\right)$$ holder.

Trinn 2

Vi antar $$ P\left(k\right):S_k = k·\frac{a_1+a_k}{2}$$.

Da må vi vise

$$ P\left(k+1\right):S_{k+1}=\left(k+1\right)·\frac{a_1+a_{k+1}}{2}$$

VS:

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

$$ \begin{array}{rcl}{S}_{k+1} & =& S_k+a_{k+1}\\ & =& S_k+a_1+dk\end{array}$$

HS:

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

$$ \begin{array}{rcl}\left(k+1\right)·\frac{a_1 +a_{k+1}}{2} & =& k·\frac{a_1 +a_{k+1}}{2}+\frac{a_1 +a_{k+1}}{2}\\ & & \\ & =& k·\frac{a_1+a_k+d}{2}+\frac{a_1+a_1+dk}{2}\\ & =& k·\frac{a_1+a_k}{2}+\frac{kd}{2}+\frac{2a_1}{2}+\frac{dk}{2}\\ & =& S_k+a_1+dk\end{array}$$

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

Konklusjon

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

Vi har at $$ a_n=a_1·k^{n-1}$$.

$$ P\left(n\right): S_n=a_1·\frac{k^n-1}{k-1}$$

Trinn 1

VS:

$$ S_1=a_1$$

HS:

$$ \begin{array}{rcl}{S}_1 & =& a_1·\frac{k^1-1}{k-1}\\ & =& a_1·\frac{k-1}{k-1}\\ & =& a_1·1\\ & =& a_1\end{array}$$

$$ P\left(1\right)$$ er sann.

Trinn 2

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

(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\left(r+1\right): S_{r+1}=a_1·\frac{k^{r+1}-1}{k-1}$$

$$ a_{r+1}=a_1·k^{r-1+1}=a_1·k^r$$

Utregning:

$$ \begin{array}{rcl}\mathrm{VS} & =& S_{r+1}\\ & =& S_r+a_{r+1}\\ & =& a_1·\frac{k^r-1}{k-1}+a_1·k^r\\ & =& a_1\left(\frac{k^r-1}{k-1}+k^r\right)\\ & =& a_1\left(\frac{k^r-1}{k-1}+\frac{k^r\left(k-1\right)}{k-1}\right)\\ & =& a_1\left(\frac{k^r-1+k^{r+1}-k^r}{k-1}\right)\\ & =& a_1\left(\frac{k^{r+1}-1}{k-1}\right)\\ & =& \mathrm{HS}\end{array}$$

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

Konklusjon

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

Vi finner først formelen.

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

$$ a_1=2$$

og

$$ \begin{array}{rcl}{a}_n & =& a_1+d\left(n-1\right)\\ & =& 2+2\left(n-1\right)\\ & =& 2+2n-2\\ & =& 2n\end{array}$$

Vi bruker formelen for sum av aritmetisk rekke:

$$ \begin{array}{rcl}{S}_n & =& n·\frac{a_1+a_n}{2}\\ & =& n·\frac{2+2n}{2}\\ & =& n·\left(1+n\right)\\ & =& n^2+n\end{array}$$

Induksjonsbeviset:

Vi skal bevise påstanden

$$ P\left(n\right):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\left(1\right)$$ holder.

Trinn 2

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

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

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

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

Konklusjon

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