Induksjonsbevis: Forskjell mellom sideversjoner
Linje 149: | Linje 149: | ||
1. Grunnlag: n=0 gir 6, som er delelig på 3. | 1. Grunnlag: n=0 gir 6, som er delelig på 3. | ||
2. Induksjonsgrunnlag: n= k+ 1 gir: $(k+1)^3 -4(k+1) + 6 = (k+1)(k^2+2k+1)-4k - 4 = $ | 2. Induksjonsgrunnlag: n= k+ 1 gir: $(k+1)^3 -4(k+1) + 6 = (k+1)(k^2+2k+1)-4k - 4 = \\ k^3-3k^2-k-3 = \\ (k^3-4k+6) + (3k^2+3k-9) $ | ||
Den første parantesen er delelig på 3, dette er vist i 1. Den andre inneholder tre ledd, alle med faktor 3, altså er uttrykket delelig på 3. | |||
</div> | </div> |
Sideversjonen fra 7. mar. 2017 kl. 16:03
Bevis ved induksjon er delt i to trinn, induksjonsgrunnlaget og induksjonstrinnet.
La U(n) være et åpent utsagn som gjelder for alle <math>\quad n \geq n_0</math>
Dersom
1. induksjonsgrunnlaget<math>\quad U(n_0)</math> er sann
og
2. induksjonstrinnet <math>\quad U(k) \Rightarrow U(k+1),\quad k\geq n_0 </math> er sann,
så er U(n) sann for alle <math>\quad n \geq n_0</math> .
Prinsippet for induksjonsbevis illustreres enklest via et konkret eksempel: La oss si at vi ønsker å bevise formelen <math>\sum_{i=1}^{n}i=\frac{n(n+1)}{2}\,\forall n \in \mathbb{N}</math>.
Steg 1
Det første vi gjør er å verifisere at formelen vi skal bevise gjelder for spesialtilfellet <math>n=1</math>. Dette er trivielt siden <math>\sum_{i=1}^{1}i=1</math> og <math>\frac{1\cdot (1+1)}{2}=1</math>; høyresiden er lik venstresiden.
Steg 2 (induksjonssteget)
I induksjonssteget antar vi at formelen gjelder for en bestemt verdi av n, si <math>n=k</math>, og utleder deretter via kjente regneregler at formelen gjelder for <math>n=k +1</math>. Dersom vi lykkes vil dette indusere en dominoeffekt; fra steg 1 vet vi at formelen gjelder for <math>n=1</math> og steg 2 sikrer at formelen gjelder for <math>n=2</math> (og på samme måte at formelen gjelder for <math>n=3</math> etc.).
I det konkrete eksempelet vil induksjonssteget se slik ut:
<math>\sum_{i=1}^{k}i=\frac{k (k+1)}{2} \\ k+1+\sum_{i=1}^{k}i= k+1+\frac{k(k+1)}{2} \\ \sum_{i=1}^{k+1}i=\frac{(k+1)(k+2)}{2} </math>
Her ser vi altså at dersom formelen er riktig for <math>n=k</math> vil formelen være riktig for <math>n=k+1</math>, og dette kompletterer induksjonsbeviset.
Denne "malen" for induksjonsbevis vil i prinsippet gjelde for alle problemer, dog vil det kunne oppstå ulike vanskeligheter for de spesifikke variasjonene, men disse er av "algebraisk" karakter. For å bli fortrolig med induksjon er man nødt til å regne gjennom endel eksempler.
Eksempel 1:
<math> 1 + 2 + 3 +.....+ k = \frac{k (k+1)}{2} \\ 1 + 2 + 3 +.....+ k + (k+1) = \frac{(k+1) ((k+1)+1)}{2} = \frac{(k+1) (k + 2)}{2} </math>
I den nederste linjen er summen av de k første leddene på venstre side gitt som høyresiden i utrykket i første linje. Man får:
<math> \frac{k (k+1)}{2} + (k+1) = \\ \frac{k (k+1)}{2}+ \frac{2 (k+1)}{2} = \\ \frac{k^2+k+2k+2}{2} = \\ \frac{k^2+3k+2}{2} = \\ \frac{(k+1)(k+2)}{2} </math>
Man observerer at dette er det samme uttrykket som høyresiden i den andre linjen man startet med. Altså er beviset fullført.
Eksempel 2:
Bevis at<math> 1^2 + 2^2 + 3^2 +.....+ n^2 = \frac{n(n+1)(2n+1)}{6} </math>
Man finner først om induksjonsgrunnlaget er sant.
<math> 1^2 = 1 \qquad \qquad \qquad \frac{1 \cdot 2 \cdot 3}{6} = 1 </math> Man ser at induksjonsgrunnlaget er sannt, begge sider er lik 1 for n=1. Ved å sett n = k og n = k+1 får man: <math> 1^2 + 2^2 + 3^2 +.....+ k^2 = \frac{k(k+1)(2k+1)}{6} </math> <math> 1^2 + 2^2 + 3^2 +.....+ k^2 + (k+1)^2 = \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6} </math> Man erstatter summen av de k første leddene i andre utsagn med høyresiden i første utsagn og får: <math> \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = </math> Det skal så vises at det over er lik <math> \frac{(k+1)(k+2)(2k+3)}{6} </math> :$\frac{k(k+1)(2k+1)}{6} + \frac{6(k+1)^2}{6} = \\ \frac{k(k+1)(2k+1) + 6(k+1)^2}{6} =\\ \frac{(k+1)(k(2k+1) + 6(k+1)}{6}= \\\frac{(k+1)(2k^2+7k+6)}{6}= \\\frac{(k+1) \cdot 2 \cdot (x+2)(x+ \frac 32)}{6}= \\ \frac{(k+1) (x+2)(2x+3)}{6} $
Som er lik høyre side: <math> \frac{(k+1)(k+2)(2k+3)}{6} </math>Q. E. D. (quod erat demonstrandum)
Eksempel 3:
Bevis at $(x^n)' = nx^{n-1}$
Induksjonsgrunnlag:
viser at formelen gjelder for n = 1:
Høyre side: $n \cdot x^{n-1} = 1 \cdot x^0 =1$
Venstre side $(x^1)'= x' =1$
( Linjen y = x har stigningstall 1 )
Grunnlaget er i orden, så:
Induksjonstrinn:
Viser at formelen holder for n= k + 1:
$(x^{k+1})' = \\ (x \cdot x^k)'= \\ x^k + x \cdot k \cdot x^{k-1} = \\ x^k + kx^k = \\ (1+k)x^k$
I tredje linje brukes produktregelen.
Q. E. D.
Eksempel 4:
Bevis at $n^3-4n+6, n \geq 0$, er delelig på 3.
1. Grunnlag: n=0 gir 6, som er delelig på 3.
2. Induksjonsgrunnlag: n= k+ 1 gir: $(k+1)^3 -4(k+1) + 6 = (k+1)(k^2+2k+1)-4k - 4 = \\ k^3-3k^2-k-3 = \\ (k^3-4k+6) + (3k^2+3k-9) $
Den første parantesen er delelig på 3, dette er vist i 1. Den andre inneholder tre ledd, alle med faktor 3, altså er uttrykket delelig på 3.