Induksjon MAT111 - H09
Induksjonsprinsippet.
La P(n) være et utsagn som gir mening for ethvert heltall n≥n0, der n0 er et fiksert heltall (ofte er n0 = 1).
For ˚a vise at P(n) er sann for alle heltall n ≥ n0 er det nok ˚a vise følgende to fakta:
(1) Utsagnet P(n) er sant n˚ar n =n0 (dvs. P(n0) er et sant utsagn).
(2) Hvis utsagnet P(n)er sant n˚ar n =k, der k er et fast men uspesifisert heltall slik at k ≥n0, s˚a holder ogs˚a P(n) n˚ar n =k+ 1 (dvs. at hvis P(k) er sant s˚a er ogs˚a P(k+ 1) sant).
Merknad. I steg 2 tar vi ikke stilling til om utsagnetP(k) virkelig er sant: vi bare viser at om P(k) er sant, s˚a er jammen P(k+ 1) sant ogs˚a. Antagelsen om atP(k) er sann kalles induksjonshypotesen.
Eksempel (Teorem 1(b) i 5.1 i læreboken)
Vis at for ethvert positivt heltall n, er summen av alle heltallene fra 1 til n lik n(n+ 1)/2, dvs. at
n
X
i=1
i= 1 + 2 + 3 +· · ·+n= n(n+ 1)
2 .
Bevis ved induksjon. Vi skal vise at utsagnet P(n)
n
X
i=1
i= 1 + 2 + 3 +· · ·+n = n(n+ 1) 2 er riktig for alle heltalln ≥1.
Først observerer vi at P(1) er riktig. Ved ˚a sette n = 1 inn i formelen, ser vi at venstresiden er da lik 1 og høyresiden er lik 1(1+1)2 = 22 = 1. (Dette er trinn 1.)
1
2
La oss n˚a anta at p˚astanden P(n) holder for n = k, der k ≥ 1, dvs. vi antar at P(k) holder, med andre ord at
(1)
k
X
i=1
i= 1 + 2 + 3 +· · ·+k= k(k+ 1) 2
(Dette er induksjonshypotesen.) Vi vil bruke dette til ˚a vise at P(k+ 1) holder. Da regner vi ut:
k+1
X
i=1
i = 1 + 2 + 3 +· · ·+k+ (k+ 1)
= (1 + 2 + 3 +· · ·+k) + (k+ 1) ved (1)
= k(k+ 1)
2 +k+ 1
= k(k+ 1) + 2(k+ 1)
2 = (k+ 1)(k+ 2)
2 .
Dette erP(n) forn=k+1. Vi har derfor vist at hvisP(k) er sant s˚a er ogs˚aP(k+1) sant og vi er ferdig.
Oppgave 1
Vis at for alle naturlige tall n er
n
X
i=1
2i−1 = 1 + 2 + 22+· · ·+ 2n−1 = 2n−1
Oppgave 2
Vis at summen av den minste oddetallene er n2, for alle naturlige tall n.
Oppgave 3 (Bernoullis ulikhet)
Vis at for alle heltall n≥0 gjelder
(1 +x)n≥1 +nx for x≥ −1.
3
Oppgave 4
Vis at
cosu·cos(2u)·cos(4u)·cos(8u)· · ·cos(2n−1u) = sin(2nu) 2nsinu for alle naturlige talln.
Oppgave 5
Vis at for alle naturlige tall n er
n
X
i=1
√1
i = 1 + 1
√2+ 1
√3· · ·+ 1
√n >2(√
n+ 1−1).
Oppgave 6
Vis at n3−n er delelig p˚a 3 for alle naturlige tall n.
Hint og løsningsforslag p˚a neste side
4
Hint til oppgavene
Oppgave 4. Bruk identiteten sin 2v = 2 sinvcosv.
Oppgave 6. At et tall er delelig p˚a 3 betyr at det kan skrives som 3a, for et heltall a.
Løsning oppgave 3
Vi viser ulikheten
(2) (1 +x)n≥1 +nx for x≥ −1.
ved induksjon og kontrollerer først at den er riktig for n = 0. Setter vi inn n = 0 i (2) f˚ar vi
1 = (1 +x)0 ≥(1 + 0·x) = 1 for x≥ −1, som er (˚apenbart) riktig.
Anta s˚a at ulikheten holder for et heltall k ≥0, dvs. anta at
(3) (1 +x)k ≥1 +kx for x≥ −1.
Multipliserer vi begge sidene medx+ 1 (som er ikkenegativ sidenx≥ −1), f˚ar vi:
(1 +x)k+1 ≥(1 +kx)(1 +x) og ved hjelp av dette f˚ar vi:
(1 +x)k+1 ≥(1 +kx)(1 +x) = 1 + (k+ 1)x+kx2 ≥1 + (k+ 1)x,
som viser at (2) er riktig for n =k+ 1. Ved induksjon følger Bernoullis ulikhet for alle heltall n≥0.
Andreas Leopold Knutsen
