NumiSum

Bevis ved induksjon

Et induksjonsbevis viser at en påstand P(n)P(n) stemmer for ALLE hele tall n≥1n \geq 1 med bare to steg. Først BASISSTEGET: vis at P(1)P(1) stemmer. Deretter INDUKSJONSSTEGET: anta at P(k)P(k) stemmer for en VILKÅRLIG kk (dette kalles induksjonshypotesen), og bruk den antakelsen til å vise at P(k+1)P(k+1) da også stemmer. Sammen fungerer de to stegene som en uendelig rekke dominobrikker: basissteget dytter den første brikken, og induksjonssteget garanterer at hver brikke velter den neste. Derfor faller ALLE brikkene, selv om vi bare beviste to ting.

Induksjonsprinsippet

P(1)P(1) sann OG (P(k)⇒P(k+1))⇒P(n)\bigl(P(k) \Rightarrow P(k+1)\bigr) \Rightarrow P(n) sann for alle n≥1n \geq 1

Summen av de n første naturlige tallene

1+2+3+⋯+n=n(n+1)21 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}

Tips

  • Glem aldri basissteget. Uten det er induksjonssteget bare en kjede av «hvis–så»-utsagn som ikke er forankret i noe sant – dominobrikkene står der, men ingen dytter den første.
  • Skriv induksjonshypotesen eksplisitt som en egen setning: «Anta at påstanden stemmer for n=kn = k.» Da ser du tydelig hva du får LOV til å bruke i neste steg, og hva du faktisk skal vise.

Eksempel: Bevis at 1 + 2 + ... + n = n(n+1)/2

Bevis ved induksjon at 1+2+3+⋯+n=n(n+1)21 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} for alle hele tall n≥1n \geq 1.

Induksjonsbeviset steg for steg
StegHva som vises
Basissteg (n = 1)1 = 1 · 22\frac{2}{2}
Induksjonshypoteseanta 1+...+k = k(k+1)/2
Legg til (k+1)k(k+1)/2 + (k+1)
Forenkle(k+1)(k+2)/2, altså P(k+1)
Løsning:
  1. Basissteg: sett n=1n = 1
  2. venstre side er 11, høyre side er 1⋅22=1\frac{1 \cdot 2}{2} = 1
  3. like, så P(1)P(1) stemmer
  4. induksjonssteg: anta at påstanden stemmer for n=kn = k, altså 1+2+⋯+k=k(k+1)21 + 2 + \cdots + k = \frac{k(k+1)}{2} (induksjonshypotesen)
  5. legg (k+1)(k+1) til begge sider: 1+2+⋯+k+(k+1)=k(k+1)2+(k+1)1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1)
  6. sett høyre side på felles brøkstrek: k(k+1)+2(k+1)2\frac{k(k+1) + 2(k+1)}{2}
  7. sett (k+1)(k+1) utenfor parentes i telleren: (k+1)(k+2)2\frac{(k+1)(k+2)}{2}
  8. dette er nøyaktig formelen med n=k+1n = k+1 satt inn, så P(k+1)P(k+1) stemmer også
  9. siden P(1)P(1) er sann og P(k)⇒P(k+1)P(k) \Rightarrow P(k+1), stemmer formelen for alle n≥1n \geq 1.
Alternativ forklaring/metode: Legg summen sammen med seg selv baklengs

Alternativ metode – innenfor pensum, men ikke hovedmetoden her

Gauss' parbevis (uten induksjon)

Denne konkrete formelen kan faktisk bevises helt UTEN induksjon, med et triks Gauss visstnok fant opp som skolegutt: skriv summen S=1+2+⋯+nS = 1 + 2 + \cdots + n to ganger, den andre gangen baklengs, og legg dem sammen ledd for ledd: S=1+2+⋯+nS = 1 + 2 + \cdots + n og S=n+(n−1)+⋯+1S = n + (n-1) + \cdots + 1. Hvert par av ledd på samme plass summerer til (n+1)(n+1), og det er nn slike par, så 2S=n(n+1)2S = n(n+1), altså S=n(n+1)2S = \frac{n(n+1)}{2}. Metoden er raskere for akkurat DENNE formelen, men fungerer ikke for de fleste andre påstander induksjon kan bevise – induksjon er det generelle verktøyet, dette er et smart spesialtriks for én bestemt sum.

Parene summerer alltid til n + 1
ForfraBakfraSum
1nn + 1
2n - 1n + 1
3n - 2n + 1

Oppgaver

Prøv minst én oppgave på hvert nivå.

Lett(3)

L-11Hva kalles steget der du viser at påstanden stemmer for det minste tallet?

Vis fasit
BeregningResultat
Induksjon starter med å forankre påstanden i n1
basissteget
  1. Induksjon starter med å forankre påstanden i n = 1
  2. basissteget

L-12Hva ANTAR vi i induksjonssteget?

Vis fasit
BeregningResultat
Induksjonssteget bruker en antakelse om n = k for å vise nk + 1
induksjonshypotesen
  1. Induksjonssteget bruker en antakelse om n = k for å vise n = k + 1
  2. induksjonshypotesen

L-13Stemmer 1+2+3=3⋅421 + 2 + 3 = \frac{3 \cdot 4}{2}?

Vis fasit
BeregningResultat
1 + 2 + 3 = 6, og 3 gange 4 delt på 26
ja, 6 = 6
  1. 1 + 2 + 3 = 6, og 3 gange 4 delt på 2 = 6
  2. ja, 6 = 6
Middels(3)

M-11Hva er k(k+1)2+(k+1)\frac{k(k+1)}{2} + (k+1) forenklet?

Vis fasit
BeregningResultat
Sett på felles brøkstrek: k(k+1) pluss 2(k+1), alt delt på 2
sett (k+1) utenfor parentes
(k + 1)(k + 2) / 2
  1. Sett på felles brøkstrek: k(k+1) pluss 2(k+1), alt delt på 2
  2. sett (k+1) utenfor parentes
  3. (k + 1)(k + 2) / 2

M-12Hva blir summen 1+2+⋯+101 + 2 + \cdots + 10 med formelen?

Vis fasit
BeregningResultat
n10 gir 10 gange 11 delt på 2
55
  1. n = 10 gir 10 gange 11 delt på 2
  2. 55

M-13Hvorfor er induksjonssteget ALENE ikke et fullstendig bevis?

Vis fasit
BeregningResultat
Uten basissteget er ingen brikke dyttet
kjeden er ikke forankret i noe sant
  1. Uten basissteget er ingen brikke dyttet
  2. kjeden er ikke forankret i noe sant
Vanskelig(3)

V-11Bevis ved induksjon at 2+4+⋯+2n=n(n+1)2 + 4 + \cdots + 2n = n(n+1). Hva er induksjonshypotesen?

Vis fasit
BeregningResultat
Rekken 2 + 4 + ... + 2n har induksjonshypotese for nk
2 + 4 + ... + 2k = k(k + 1)
  1. Rekken 2 + 4 + ... + 2n har induksjonshypotese for n = k
  2. 2 + 4 + ... + 2k = k(k + 1)

V-12I induksjonssteget over: hva blir k(k+1)+2(k+1)k(k+1) + 2(k+1) forenklet?

Vis fasit
BeregningResultat
Sett (k+1) utenfor parentes: k(k+1) pluss 2(k+1)
(k + 1)(k + 2)
  1. Sett (k+1) utenfor parentes: k(k+1) pluss 2(k+1)
  2. (k + 1)(k + 2)

V-13Hvorfor beviser induksjon påstanden for ALLE n≥1n \geq 1, og ikke bare n=1n = 1 og n=kn = k?

Vis fasit
BeregningResultat
P(1) sann og P(k) gir P(k+1) for enhver k
kjeden fortsetter uendelig
alle n er dekket
  1. P(1) sann og P(k) gir P(k+1) for enhver k
  2. kjeden fortsetter uendelig
  3. alle n er dekket