matematikk.net

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?

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.