Induksjonsbevis: Forskjell mellom sideversjoner

Fra Matematikk.net
Hopp til: navigasjon, søk
Linje 86: Linje 86:
<p></p>
<p></p>
Man finner først om induksjonsgrunnlaget er sannt.
Man finner først om induksjonsgrunnlaget er sannt.
<tex> 1^2 = 1  \qquad \frac{1 \cdot 2 \cdot 3)}{6} = 1 </tex>
<tex> 1^2 = 1  \qquad  \qquad \qquad \frac{1 \cdot 2 \cdot 3}{6} = 1 </tex>
Man ser at induksjonsgrunnlaget er sannt, begge sider er lik 1 for n=1.
Man ser at induksjonsgrunnlaget er sannt, begge sider er lik 1 for n=1.
</blockquote>
</blockquote>

Sideversjonen fra 14. jun. 2010 kl. 07:19

Bevis ved induksjon er delt i to trinn, induksjonsgrunnlaget og induksjonstrinnet.


La U(n) være et åpent utsagn som gjelder for alle <tex>\quad n \geq n_0</tex>

Dersom

1. induksjonsgrunnlaget<tex>\quad U(n_0)</tex> er sann

og

2. induksjonstrinnet <tex>\quad U(k) \Rightarrow U(k+1),\quad k\geq n_0 </tex> er sann,

så er U(n) sann for alle <tex>\quad n \geq n_0</tex> .



Prinsippet for induksjonsbevis illustreres enklest via et konkret eksempel: La oss si at vi ønsker å bevise formelen <tex>\sum_{i=1}^{n}i=\frac{n(n+1)}{2}\,\forall n \in \mathbb{N}</tex>.


Steg 1

Det første vi gjør er å verifisere at formelen vi skal bevise gjelder for spesialtilfellet <tex>n=1</tex>. Dette er trivielt siden <tex>\sum_{i=1}^{1}i=1</tex> og <tex>\frac{1\cdot (1+1)}{2}=1</tex>; høyresiden er lik venstresiden.


Steg 2 (induksjonssteget)

I induksjonssteget antar vi at formelen gjelder for en bestemt verdi av n, si <tex>n=k</tex>, og utleder deretter via kjente regneregler at formelen gjelder for <tex>n=k +1</tex>. Dersom vi lykkes vil dette indusere en dominoeffekt; fra steg 1 vet vi at formelen gjelder for <tex>n=1</tex> og steg 2 sikrer at formelen gjelder for <tex>n=2</tex> (og på samme måte at formelen gjelder for <tex>n=3</tex> etc.).


I det konkrete eksempelet vil induksjonssteget se slik ut:


<tex>\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} </tex>


Her ser vi altså at dersom formelen er riktig for <tex>n=k</tex> vil formelen være riktig for <tex>n=k+1</tex>, 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:



La oss se litt nærmere på eksemplet over, denne gangen uten bruk av summetegn.

<tex> 1 + 2 + 3 +.....+ n = \frac{n (n+1)}{2} </tex>

n skal vare et positivt helt tall.

Først undersøker man induksjonsgrunnlaget. n = 1 gir høyre side lik venstre side.

Induksjonstrinne:

<tex> 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} </tex>

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:

<tex> \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} </tex>

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

<tex> 1^2 + 2^2 + 3^2 +.....+ n^2 = \frac{n(n+1)(2n+1)}{6} </tex>

Man finner først om induksjonsgrunnlaget er sannt. <tex> 1^2 = 1 \qquad \qquad \qquad \frac{1 \cdot 2 \cdot 3}{6} = 1 </tex> Man ser at induksjonsgrunnlaget er sannt, begge sider er lik 1 for n=1.