Jeg skjønner induksjon, jeg skjønner bruken og jeg skjønner tankegangen.
Men denne oppgaven.
(1*2*3*...*(2n-1)) / 1*2*3*...*n <= 2^n for alle naturlige tall n
Hva er trikset her, hvordan utnytter jeg induksjonshypotesen slik at jeg får bevist dette?
Jeg har forsøkt å multiplisere ind.hypotesen med 2, for å få
2(2n-1)/2n <= 2^(n+1) og det er forsåvidt greit nok... men jeg mangler et steg her.
Hjelp?
Induksjonsbevis
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
Gjest
Du skal altså visa at
1 * 3 * 5 * ... * (2n - 1)/(1 * 2 * ... *n) <= 2^n for alle naturlege tal n.
[Du hadde teke med 2 i tellaren. Reknar med at det er ein tastefeil.]
Dette kan omskrivast til
VS = (2n)!/(n! * 2 * 4 * ... * (2n) = (2n)!/(2^n * (n!)^2) <= 2^n = HS
som er ekvivalent med (2n)!/((n!)^2) <= 2^(2n)
KOMBINATORISK BEVIS
Me har 2n kandidatar, og skal plukka ut ei viss mengd av dei. To utvalsmetodar er:
Metode 1: Plukka ut presis n stykk. (2n)!/((n!)^2) ulike måtar.
Metode 2: Plukka ut kor mange ein enn vil. 2^(2n) ulike måtar.
Metode 2 gjev naturlegvis minst like mange alternativ som metode 1, og resultatet følgjer. [Me ser lett at resultatet ikkje er særleg sterkt.]
INDUKSJONSBEVIS
Setninga er korrekt for n = 1. Anta at den er korrekt for n = k. Då har me
for k + 1
VS[sub]k + 1[/sub] = VS[sub]k[/sub] * (2k + 1)/(k + 1) <= 2^k * 2 = 2^(k + 1), sidan
(2k + 1)/(k + 1) = 2 - 1/(k + 1) < 2.
der VS[sub]m[/sub] = 1 * 3 * 5 * ... * (2m - 1)/(1 * 2 * ... *m).
RETT-FRAM-BEVIS
VS kan omformast til
1/1 * 3/2 * ... * (2k - 1)/k * ... * (2n - 1)/n < 2^(n - 1) < 2^n.
1 * 3 * 5 * ... * (2n - 1)/(1 * 2 * ... *n) <= 2^n for alle naturlege tal n.
[Du hadde teke med 2 i tellaren. Reknar med at det er ein tastefeil.]
Dette kan omskrivast til
VS = (2n)!/(n! * 2 * 4 * ... * (2n) = (2n)!/(2^n * (n!)^2) <= 2^n = HS
som er ekvivalent med (2n)!/((n!)^2) <= 2^(2n)
KOMBINATORISK BEVIS
Me har 2n kandidatar, og skal plukka ut ei viss mengd av dei. To utvalsmetodar er:
Metode 1: Plukka ut presis n stykk. (2n)!/((n!)^2) ulike måtar.
Metode 2: Plukka ut kor mange ein enn vil. 2^(2n) ulike måtar.
Metode 2 gjev naturlegvis minst like mange alternativ som metode 1, og resultatet følgjer. [Me ser lett at resultatet ikkje er særleg sterkt.]
INDUKSJONSBEVIS
Setninga er korrekt for n = 1. Anta at den er korrekt for n = k. Då har me
for k + 1
VS[sub]k + 1[/sub] = VS[sub]k[/sub] * (2k + 1)/(k + 1) <= 2^k * 2 = 2^(k + 1), sidan
(2k + 1)/(k + 1) = 2 - 1/(k + 1) < 2.
der VS[sub]m[/sub] = 1 * 3 * 5 * ... * (2m - 1)/(1 * 2 * ... *m).
RETT-FRAM-BEVIS
VS kan omformast til
1/1 * 3/2 * ... * (2k - 1)/k * ... * (2n - 1)/n < 2^(n - 1) < 2^n.