Induksjonsbevis
Posted: 07/12-2006 13:09
Hei igjen.
Har akkurat hatt eksamen (MAT-INF1100), og det gikk så som så.
Håper det jeg leverte kvalifiserer til en C!
En av oppgavene var et induksjonsbevis for en differensligning.
Hvis noen kan sjekke om det jeg besvarte virker greit hadde det vært knall!
Oppgave
Vi har en gitt differensligning:
[tex]x_n = \frac{x_{n-1}}{2} + \frac{1}{n}[/tex] der [tex]x_0 = 0[/tex]
Vis ved induksjon at
[tex]x_n \leq 1[/tex] for alle [tex]n \g 0[/tex]
Besvarelse
(I)
Vi sjekker om påstanden stemmer:
[tex]x_1 = \frac{x_0}{2} + \frac{1}{1} = \frac{0}{2} + \frac{1}{1} = 1[/tex]
Og siden jeg er litt tøffere enn alle andre, tar jeg en til:
[tex]x_2 = \frac{x_1}{2} + \frac{1}{2} = \frac{1}{2} + \frac{1}{2} = 1[/tex]
(II)
Vi ser at dette stemmer for k, og vil bevise at det da også stemmer for k + 1:
[tex]x_{k+1} = \frac{x_k}{2} + \frac{1}{(k+1)}[/tex]
Vi har da fra induksjonshypotesen at x_k aldri er større enn 1. Vi setter derfor in x_k = 1.
[tex]x_{k+1} = \frac{1}{2} + \frac{1}{(k+1)}[/tex]
Felles nevner:
[tex]x_{k+1} = \frac{k+1}{2k+2} + \frac{2}{2k+2}[/tex]
[tex]x_{k+1} = \frac{2 + (k+1)}{2(k+1)}[/tex]
Vi ser at 2(k+1) alltid er større enn 2 + (k+1), og har da at x_(k+1) aldri blir større enn 1, og beviset er fullført.
Sånn! Blir dette riktig?
Har akkurat hatt eksamen (MAT-INF1100), og det gikk så som så.
Håper det jeg leverte kvalifiserer til en C!
En av oppgavene var et induksjonsbevis for en differensligning.
Hvis noen kan sjekke om det jeg besvarte virker greit hadde det vært knall!
Oppgave
Vi har en gitt differensligning:
[tex]x_n = \frac{x_{n-1}}{2} + \frac{1}{n}[/tex] der [tex]x_0 = 0[/tex]
Vis ved induksjon at
[tex]x_n \leq 1[/tex] for alle [tex]n \g 0[/tex]
Besvarelse
(I)
Vi sjekker om påstanden stemmer:
[tex]x_1 = \frac{x_0}{2} + \frac{1}{1} = \frac{0}{2} + \frac{1}{1} = 1[/tex]
Og siden jeg er litt tøffere enn alle andre, tar jeg en til:
[tex]x_2 = \frac{x_1}{2} + \frac{1}{2} = \frac{1}{2} + \frac{1}{2} = 1[/tex]
(II)
Vi ser at dette stemmer for k, og vil bevise at det da også stemmer for k + 1:
[tex]x_{k+1} = \frac{x_k}{2} + \frac{1}{(k+1)}[/tex]
Vi har da fra induksjonshypotesen at x_k aldri er større enn 1. Vi setter derfor in x_k = 1.
[tex]x_{k+1} = \frac{1}{2} + \frac{1}{(k+1)}[/tex]
Felles nevner:
[tex]x_{k+1} = \frac{k+1}{2k+2} + \frac{2}{2k+2}[/tex]
[tex]x_{k+1} = \frac{2 + (k+1)}{2(k+1)}[/tex]
Vi ser at 2(k+1) alltid er større enn 2 + (k+1), og har da at x_(k+1) aldri blir større enn 1, og beviset er fullført.
Sånn! Blir dette riktig?
