Matematik
Induktionsbevis - et lille hint
Hej
Jeg er i gang med en aflevering hvor der også indgår en opgave omkring induktionsbevis. Jeg er løbet ind i en mur, og har lige brug for et par hints.
Opgaven lyder:
Bevis: P(n): n*3n≤4n-2 er sand for alle n>=7
Basissteppet er jo nemt nok:
P(7); 7*37≤47-2
= 15309≤16382
Hvilket er sandt.
Vi antager så, at P(k): n*3k≤4k-2 er sand og skal vise, at så må P(k+1) også være sand.
P(k+1): (k+1)*3(k+1) ≤ 4(k+1)-2
Hvis jeg regner på venstresiden, så får jeg:
(k+1)*3(k+1)=(k+1)(3*3k) = 3k+3+k*3k+3k = (k*3k )+3+3k+3k
Og så stopper jeg.... Det ses, at P(k) findes i sidste sætning, men hvordan kommer jeg videre?
Håber der er nogen, der kan hjælpe :)
Svar #1
15. september 2012 af Andersen11 (Slettet)
Din udregning er ikke korrekt.
(k+1)(3·3k) = k·3·3k + 3·3k
Man antager, at P(n) er sand for et n ≥ 7, dvs
n·3n ≤ 4n - 2 .
Vi har så
(n+1)·3n+1 = (n+1)·3n·3 = n·3n·3 + 3n·3 ≤ (4n -2)·3 + 3n·3
= 4n·3 -6 + 3n·3
= 4n+1 - 2 + 4n·3 -6 + 3n·3 - 4n+1 + 2
= 4n+1 - 2 + 4n·3 -4 +3n·3 -4n+1
= 4n+1 - 2 -4n -4 + 3n·3
= 4n+1 -2 - (4n + 4 - 3n+1)
Da n ≥ 7, vil der gælde
3·3n ≤ (n/2)·3n ≤ (4n -2)/2 = 2·4n-1 -1 ≤ 2·4n-1 + 2 = 2·(4n-1 +1) ≤ 4·(4n-1 + 1) = 4n + 4
Altså er 4n + 4 - 3n+1 ≥ 0 , og derfor er
4n+1 -2 - (4n + 4 - 3n+1) ≤ 4n+1 -2 ,
hvorfor
(n+1)·3n+1 ≤ 4n+1 -2
Svar #2
16. september 2012 af paarse (Slettet)
Tusind tak.
Jeg kan godt se, at jeg havde lavet en regnefejl.
Vil du knytte et par ord til de forskellige trin du udfører?
Svar #3
17. september 2012 af LuckyLuc (Slettet)
Hej igen, jeg har en hurtig kommentar til højre siden ved:
≤ (4n -2)·3 + 3n·3
Er dette ikke 4n +1- 2, og hvordan bliver til ≤ (4n -2)·3 + 3n·3?
Ligemeget kan godt se hvor du har det fra nu. Sry for hijack af tråden
Svar #4
17. september 2012 af Andersen11 (Slettet)
#3
Nej. Man kan jo kun benytte, at P(n) er sand, dvs.
n·3n ≤ 4n - 2
og derfra skal man vise, at P(n+1) er sand. Det er gennemgået i detaljer ovenfor.
Skriv et svar til: Induktionsbevis - et lille hint
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.