Forskjell mellom versjoner av «Induksjonsbevis»
m (Retter egen feilplassert kategorisering) |
|||
(57 mellomliggende revisjoner av 3 brukere er ikke vist) | |||
Linje 1: | Linje 1: | ||
− | Bevis ved induksjon er delt i to trinn, induksjonsgrunnlaget og | + | Bevis ved induksjon er delt i to trinn, induksjonsgrunnlaget og induksjonsstrinnet. |
<p></p> | <p></p> | ||
+ | <div style="padding: 1em; border: 1px blue; background-color: #C9EFF8;"> | ||
− | La U(n) være et åpent utsagn som gjelder for alle < | + | La <math>U(n)</math> være et åpent utsagn som gjelder for alle <math>n \geq n_0</math> |
<p></p> | <p></p> | ||
Linje 9: | Linje 10: | ||
Dersom | Dersom | ||
<p></p> | <p></p> | ||
− | 1. induksjonsgrunnlaget U( | + | 1. induksjonsgrunnlaget <math>U(n_0)</math> er sann |
− | + | <p></p> | |
og | og | ||
<p></p> | <p></p> | ||
− | |||
− | + | 2. induksjonstrinnet <math>U(k) \Rightarrow U(k+1),\quad k\geq n_0 </math> er sann, | |
<p></p> | <p></p> | ||
− | så er U(n) sann for alle n | + | så er <math>U(n)</math> sann for alle <math>n \geq n_0.</math> |
+ | <p></p> | ||
+ | |||
+ | </div> | ||
+ | |||
+ | |||
+ | |||
+ | Prinsippet for induksjonsbevis illustreres enklest via et konkret eksempel: La oss si at vi ønsker å bevise formelen | ||
+ | |||
+ | \[ \sum_{i=1}^{n}i=\frac{n(n+1)}{2}\, \qquad \forall n \in \mathbb{N} \] | ||
+ | |||
+ | |||
+ | == Trinn 1 == | ||
+ | Det første vi gjør er å verifisere at formelen 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. | ||
+ | |||
+ | |||
+ | == Trinn 2 (induksjonstrinnet)== | ||
+ | I induksjonstrinnet antar vi at formelen gjelder for en bestemt verdi av n, si <math>n=k</math> og utleder deretter via kjente regneregler at formelen også gjelder for <math>n=k+1</math>. | ||
+ | Dersom vi lykkes, vil dette indusere en dominoeffekt: Fra '''trinn 1''' vet vi at formelen gjelder for <math>n=1</math> og '''trinn 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 induksjonstrinnet se slik ut: | ||
+ | |||
+ | Vi antar at formelen er riktig for <math>n=k</math>: | ||
+ | |||
+ | \[ | ||
+ | \sum_{i=1}^{k}i=\frac{k (k+1)}{2} | ||
+ | \] | ||
+ | |||
+ | Vi undersøker så summen når <math>n=k+1</math> ved å bruke denne antagelsen: | ||
+ | |||
+ | \[ | ||
+ | \begin{aligned} | ||
+ | \sum_{i=1}^{k+1}i &= \sum_{i=1}^{k}i + (k+1) \\ | ||
+ | &= \frac{k(k+1)}{2} + (k+1) \\ | ||
+ | &= \frac{(k+1)(k+2)}{2} | ||
+ | \end{aligned} | ||
+ | \] | ||
+ | |||
+ | Her ser vi altså at dersom formelen er riktig for <math>n=k</math>, så vil formelen være riktig for <math>n=k+1</math>. 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 en del eksempler. | ||
+ | |||
+ | |||
+ | |||
+ | <div style="padding: 1em; border: 1px blue; background-color: #F8ADB6;"> | ||
+ | |||
+ | '''Eksempel 1:''' | ||
+ | |||
+ | <p></p> | ||
+ | |||
+ | La oss se litt nærmere på eksemplet over, denne gangen uten bruk av summetegn: | ||
+ | |||
+ | \[ | ||
+ | 1 + 2 + 3 + \ldots + \ n = \frac{n (n+1)}{2} | ||
+ | \] | ||
+ | |||
+ | Tallet n skal være et positivt helt tall. <p></p> | ||
+ | |||
+ | Først undersøker man induksjonsgrunnlaget: Når n = 1 blir høyre side lik venstre side.<p></p> | ||
+ | |||
+ | I induksjonstrinnet antar vi først at formelen er riktig for n = k: | ||
+ | |||
+ | \[ | ||
+ | 1 + 2 + 3 + \ldots + k = \frac{k (k+1)}{2} | ||
+ | \] | ||
+ | |||
+ | Deretter undersøker vi summen for n = k + 1, ved å bruke antagelsen: | ||
+ | |||
+ | \[ | ||
+ | \begin{aligned} | ||
+ | 1 + 2 + 3 + \ldots + k + (k+1) &= \frac{k (k+1)}{2} + (k+1) \\ | ||
+ | &=(k+1) ( \frac{k}{2} + 1) \\ | ||
+ | &= \frac{(k+1)(k + 2)}{2} | ||
+ | \end{aligned} | ||
+ | \] | ||
+ | |||
+ | Vi ser at den siste linjen er høyresiden i formelen når n = k + 1. Altså er beviset fullført. | ||
+ | </div> | ||
+ | |||
+ | |||
+ | <div style="padding: 1em; border: 1px blue; background-color: #F8ADB6;"> | ||
+ | |||
+ | '''Eksempel 2:''' | ||
+ | |||
+ | <p></p> | ||
+ | Bevis formelen | ||
+ | |||
+ | \[ | ||
+ | 1^2 + 2^2 + 3^2 +.....+ n^2 = \frac{n(n+1)(2n+1)}{6} \qquad n \in \mathbb{N} | ||
+ | \] | ||
+ | |||
+ | Man finner først om induksjonsgrunnlaget er sant. Når n = 1 er venstre side lik | ||
+ | <math> 1^2 = 1,</math> og høyre side er <math> \frac{1 \cdot 2 \cdot 3}{6} = 1.</math> | ||
+ | Induksjonsgrunnlaget er dermed sant, begge sider er lik 1 for n=1. | ||
<p></p> | <p></p> | ||
+ | I induksjonstrinnet antar vi først at formelen er riktig for n = k: | ||
+ | |||
+ | \[ | ||
+ | 1^2 + 2^2 + 3^2 + \ldots + k^2 = \frac{k(k+1)(2k+1)}{6} | ||
+ | \] | ||
+ | |||
+ | Så undersøker vi summen for n = k + 1 ved å bruke antagelsen: | ||
+ | |||
+ | \[ | ||
+ | \begin{aligned} | ||
+ | 1^2 + 2^2 + 3^2 +.....+ k^2 + (k+1)^2 &= \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \\ | ||
+ | &= (k+1) [ \frac{k(2k+1)}{6} + (k+1) ] \\ | ||
+ | &= (k+1) \frac{k[2k+1 + 6(k+1)]}{6} \\ | ||
+ | &= \frac{(k+1)[2k^2+7k+6]}{6} \\ | ||
+ | &= \frac{(k+1)[2(k+2)(k + \frac{3}{2})]}{6} \\ | ||
+ | &= \frac{(k+1)(k+2)(2k + 3)}{6} \\ | ||
+ | \end{aligned} | ||
+ | \] | ||
+ | |||
+ | Den siste linjen er høyresiden i formelen når n = k + 1. | ||
+ | |||
+ | Q.E.D. (quod erat demonstrandum) | ||
+ | </div> | ||
+ | |||
+ | |||
+ | <div style="padding: 1em; border: 1px blue; background-color: #F8ADB6;"> | ||
+ | |||
+ | '''Eksempel 3:''' | ||
+ | |||
+ | Bevis derivasjonsregelen $(x^n)' = nx^{n-1}.$ | ||
+ | |||
+ | I induksjonsgrunnlaget viser vi først 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$ | ||
+ | |||
+ | Induksjonsgrunnlaget er sann: Linjen y = x har stigningstall 1. | ||
+ | |||
+ | I induksjonstrinnet antar vi som vanlig at formelen er riktig for n = k: | ||
+ | \[ | ||
+ | (x^k)' = kx^{k-1} | ||
+ | \] | ||
+ | Vi viser så at formelen holder for n = k + 1, ved å bruke antagelsen sammen med regelen for derivering av et produkt: | ||
+ | \[ | ||
+ | \begin{aligned} | ||
+ | (x^{k+1})' &= (x \cdot x^k)' \\ | ||
+ | &= x^k + x \cdot k \cdot x^{k-1} \\ | ||
+ | &= x^k + kx^k \\ | ||
+ | &= (1+k)x^k | ||
+ | \end{aligned} | ||
+ | \] | ||
− | + | Q.E.D. | |
+ | </div> | ||
− | |||
− | |||
+ | <div style="padding: 1em; border: 1px blue; background-color: #F8ADB6;"> | ||
+ | '''Eksempel 4:''' | ||
− | + | Bevis at $n^3-4n+6$ er delelig på 3 når n er et ikke-negativt heltall. | |
− | |||
+ | 1. Induksjonsgrunnlag: n=0 gir $n^3-4n+6 = 6$, som er delelig på 3. | ||
− | + | 2. Induksjonstrinnet: Anta at $n^3-4n+6$ er delelig på 3 når n = k. Med n = k + 1 får vi | |
+ | \[ | ||
+ | \begin{aligned} | ||
+ | (k+1)^3 -4(k+1) + 6 &= (k+1)(k^2 + 2k + 1)- (4k + 4) + 6 \\ | ||
+ | &= (k^3 + 2k^2 + k + k^2 + 2k + 1) - 4k + 2 \\ | ||
+ | &= (k^3 -4k + 6) + 3(k^2 + k - 1) | ||
+ | \end{aligned} | ||
+ | \] | ||
− | + | Den første parantesen er delelig på 3, i følge antagelsen for n = k. Den andre inneholder faktoren 3. Sammen gir dette at hele uttrykket er delelig på 3. | |
+ | </div> | ||
− | |||
+ | ---- | ||
+ | [[R2 Hovedside|Tilbake til R2 Hovedside]] | ||
− | + | [[Kategori:Algebra]] | |
+ | [[Kategori:R2]] | ||
+ | [[Kategori:Ped]] | ||
+ | [[Kategori:Lex]] |
Nåværende revisjon fra 25. okt. 2019 kl. 14:51
Bevis ved induksjon er delt i to trinn, induksjonsgrunnlaget og induksjonsstrinnet.
La <math>U(n)</math> være et åpent utsagn som gjelder for alle <math>n \geq n_0</math>
Dersom
1. induksjonsgrunnlaget <math>U(n_0)</math> er sann
og
2. induksjonstrinnet <math>U(k) \Rightarrow U(k+1),\quad k\geq n_0 </math> er sann,
så er <math>U(n)</math> sann for alle <math>n \geq n_0.</math>
Prinsippet for induksjonsbevis illustreres enklest via et konkret eksempel: La oss si at vi ønsker å bevise formelen
\[ \sum_{i=1}^{n}i=\frac{n(n+1)}{2}\, \qquad \forall n \in \mathbb{N} \]
Trinn 1
Det første vi gjør er å verifisere at formelen 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.
Trinn 2 (induksjonstrinnet)
I induksjonstrinnet antar vi at formelen gjelder for en bestemt verdi av n, si <math>n=k</math> og utleder deretter via kjente regneregler at formelen også gjelder for <math>n=k+1</math>. Dersom vi lykkes, vil dette indusere en dominoeffekt: Fra trinn 1 vet vi at formelen gjelder for <math>n=1</math> og trinn 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 induksjonstrinnet se slik ut:
Vi antar at formelen er riktig for <math>n=k</math>:
\[ \sum_{i=1}^{k}i=\frac{k (k+1)}{2} \]
Vi undersøker så summen når <math>n=k+1</math> ved å bruke denne antagelsen:
\[ \begin{aligned} \sum_{i=1}^{k+1}i &= \sum_{i=1}^{k}i + (k+1) \\ &= \frac{k(k+1)}{2} + (k+1) \\ &= \frac{(k+1)(k+2)}{2} \end{aligned} \]
Her ser vi altså at dersom formelen er riktig for <math>n=k</math>, så vil formelen være riktig for <math>n=k+1</math>. 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 en del eksempler.
Eksempel 1:
La oss se litt nærmere på eksemplet over, denne gangen uten bruk av summetegn:
\[ 1 + 2 + 3 + \ldots + \ n = \frac{n (n+1)}{2} \]
Tallet n skal være et positivt helt tall. Først undersøker man induksjonsgrunnlaget: Når n = 1 blir høyre side lik venstre side.I induksjonstrinnet antar vi først at formelen er riktig for n = k:
\[ 1 + 2 + 3 + \ldots + k = \frac{k (k+1)}{2} \]
Deretter undersøker vi summen for n = k + 1, ved å bruke antagelsen:
\[ \begin{aligned} 1 + 2 + 3 + \ldots + k + (k+1) &= \frac{k (k+1)}{2} + (k+1) \\ &=(k+1) ( \frac{k}{2} + 1) \\ &= \frac{(k+1)(k + 2)}{2} \end{aligned} \]
Vi ser at den siste linjen er høyresiden i formelen når n = k + 1. Altså er beviset fullført.
Eksempel 2:
Bevis formelen
\[ 1^2 + 2^2 + 3^2 +.....+ n^2 = \frac{n(n+1)(2n+1)}{6} \qquad n \in \mathbb{N} \]
Man finner først om induksjonsgrunnlaget er sant. Når n = 1 er venstre side lik <math> 1^2 = 1,</math> og høyre side er <math> \frac{1 \cdot 2 \cdot 3}{6} = 1.</math> Induksjonsgrunnlaget er dermed sant, begge sider er lik 1 for n=1.
I induksjonstrinnet antar vi først at formelen er riktig for n = k:
\[ 1^2 + 2^2 + 3^2 + \ldots + k^2 = \frac{k(k+1)(2k+1)}{6} \]
Så undersøker vi summen for n = k + 1 ved å bruke antagelsen:
\[ \begin{aligned} 1^2 + 2^2 + 3^2 +.....+ k^2 + (k+1)^2 &= \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \\ &= (k+1) [ \frac{k(2k+1)}{6} + (k+1) ] \\ &= (k+1) \frac{k[2k+1 + 6(k+1)]}{6} \\ &= \frac{(k+1)[2k^2+7k+6]}{6} \\ &= \frac{(k+1)[2(k+2)(k + \frac{3}{2})]}{6} \\ &= \frac{(k+1)(k+2)(2k + 3)}{6} \\ \end{aligned} \]
Den siste linjen er høyresiden i formelen når n = k + 1.
Q.E.D. (quod erat demonstrandum)
Eksempel 3:
Bevis derivasjonsregelen $(x^n)' = nx^{n-1}.$
I induksjonsgrunnlaget viser vi først 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$
Induksjonsgrunnlaget er sann: Linjen y = x har stigningstall 1.
I induksjonstrinnet antar vi som vanlig at formelen er riktig for n = k:
\[ (x^k)' = kx^{k-1} \]
Vi viser så at formelen holder for n = k + 1, ved å bruke antagelsen sammen med regelen for derivering av et produkt:
\[ \begin{aligned} (x^{k+1})' &= (x \cdot x^k)' \\ &= x^k + x \cdot k \cdot x^{k-1} \\ &= x^k + kx^k \\ &= (1+k)x^k \end{aligned} \]
Q.E.D.
Eksempel 4:
Bevis at $n^3-4n+6$ er delelig på 3 når n er et ikke-negativt heltall.
1. Induksjonsgrunnlag: n=0 gir $n^3-4n+6 = 6$, som er delelig på 3.
2. Induksjonstrinnet: Anta at $n^3-4n+6$ er delelig på 3 når n = k. Med n = k + 1 får vi
\[ \begin{aligned} (k+1)^3 -4(k+1) + 6 &= (k+1)(k^2 + 2k + 1)- (4k + 4) + 6 \\ &= (k^3 + 2k^2 + k + k^2 + 2k + 1) - 4k + 2 \\ &= (k^3 -4k + 6) + 3(k^2 + k - 1) \end{aligned} \]
Den første parantesen er delelig på 3, i følge antagelsen for n = k. Den andre inneholder faktoren 3. Sammen gir dette at hele uttrykket er delelig på 3.