Induktionsbevis

Hej,

Frågan lyder: Visa att $(\begin{matrix} 2 n \\ n \end{matrix}) < 2^{2 n - 2} f ö r a l l a n \geq 5$

Jag väljer att bevisa olikheten genom ett induktionsbevis.

Basfall:

Jag visar att olikheten gäller för n = 5:

$(\begin{matrix} 10 \\ 5 \end{matrix}) = 252 < 2^{8} = 256$

Induktionsantagande:

Jag antar att olikheten $(\begin{matrix} 2 k \\ k \end{matrix}) < 2^{2 k - 2} g ä l l e r f ö r n å g o t k \geq 5$

Induktionssteg:

Jag vill visa att $(\begin{matrix} 2 (k + 1) \\ k + 1 \end{matrix}) < 2^{2 (k + 1) - 2}$

Jag skriver om båda leden och får den ekvivalenta olikheten:

$\frac{(2 k + 2) (2 k + 1)}{{(k + 1)}^{2}} (\begin{matrix} 2 k \\ k \end{matrix}) < 4 \cdot 2^{2 k - 2}$

Enligt mitt induktionsantagande så gäller att $(\begin{matrix} 2 k \\ k \end{matrix}) < 2^{2 k - 2}$

Det medför att om $\frac{(2 k + 2) (2 k + 1)}{{(k + 1)}^{2}} \leq 4$ så gäller olikheten även för k+1 (Stämmer detta?)

Det är nu det krånglar till sig för mig. Jag kan visa att olikheten gäller för $k = 5$ , samt att olikheten gäller då $k \to \infty$ . Men jag kan inte visa att den gäller för allting där i mellan. Hur ska jag gå tillväga för att visa detta?

matterolf123 skrev:
Det medför att om $\frac{(2 k + 2) (2 k + 1)}{{(k + 1)}^{2}} \leq 4$ så gäller olikheten även för k+1 (Stämmer detta?)

Det är nu det krånglar till sig för mig. Jag kan visa att olikheten gäller för $k = 5$ , samt att olikheten gäller då $k \to \infty$ . Men jag kan inte visa att den gäller för allting där i mellan. Hur ska jag gå tillväga för att visa detta?

Förenkla ditt bråk. Vad får du då?

Då får jag $\frac{2 (2 k + 1)}{k + 1} \leq 4$

Japp. Det bråket är ju nästan 4. Vad är det som skiljer?

Nu har jag klurat på det du sa men tror inte jag riktigt förstår vad du menar...

Täljaren är 4k+2. Om den hade varit 4k+4 i stället, så hade bråket varit exakt lika med 4.

Då förstår jag. Skulle man kunna formulera det som att $\frac{4 k + 2}{k + 1} < \frac{4 k + 4}{k + 1} = 4$ , och att olikheten då gäller?

Tillägg: 27 nov 2022 21:37

alternativt. $\frac{4 k + 2}{k + 1} \leq 4 = \frac{4 k + 4}{k + 1}$

Skriver om min lösning som: Det medför att om $\frac{(2 k + 2) (2 k + 1)}{k + 1} \leq 4$ så gäller olikheten även för k+1. Olikheten kan skrivas om som $\frac{4 k + 2}{k + 1} \leq \frac{4 k + 4}{k + 1}$ . Denna olikhet gäller alltid, därför gäller olikheten även för k+1.

Tack för hjälpen.

Javisst.

Det kräver visserligen att k är positivt, men det vi vet ju att k är.

Svara Avbryt

Visa senaste svar