Vollständige Induktion zu Binomialkoeffizienten (2n über n) < 2 hoch 2(n-1)

Question

Ich habe immer Probleme mit der vollständigen Induktion kann mir jemand bei der Aufgabe helfen;

Beweisen sie per Vollständige Induktion, dass

(2n über n) < 2 ^2(n-1)    

für alle n aus N  mit n >= 5

Danke

Answer 1

(10 über 5) = 252  < 256 = 2⁸ =  2^2*(5-1)  klappt !

Gelte für ein n≥5  $\begin{pmatrix} 2n\\n \end{pmatrix} \lt 2^{2 \cdot (n-1)}$ #

Dann hat man:   $\begin{pmatrix} 2(n+1)\\n+1 \end{pmatrix} = \begin{pmatrix} 2n+2\\n+1 \end{pmatrix} = \begin{pmatrix} 2n+1\\n \end{pmatrix}+\begin{pmatrix} 2n+1\\n+1 \end{pmatrix}$

$= \begin{pmatrix} 2n\\n \end{pmatrix}+\begin{pmatrix} 2n\\n-1 \end{pmatrix} + \begin{pmatrix} 2n\\n \end{pmatrix}+\begin{pmatrix} 2n\\n+1 \end{pmatrix}$

$= 2 \cdot ( \begin{pmatrix} 2n\\n-1 \end{pmatrix} + \begin{pmatrix} 2n\\n \end{pmatrix})$

Wegen $= \begin{pmatrix} 2n\\n-1 \end{pmatrix} \lt \begin{pmatrix} 2n\\n \end{pmatrix}$ geht es weiter mit

$\lt 2 \cdot ( 2 \cdot \begin{pmatrix} 2n\\n \end{pmatrix}) = 4 \cdot \begin{pmatrix} 2n\\n \end{pmatrix}$  mit # gibt das

$\lt 4 \cdot 2^{2 \cdot (n-1)} = 2^{2 \cdot ((n+1)-1)}$

Answer 2

Induktionsanfang: Zeige dass

        ${2n\choose n} < 2^{2(n-1)}$

für $n = 5$ gilt.

Induktionsschritt: Sei $n \geq 5$ mit ${2n\choose n} < 2^{2(n-1)}$.

Zeige, dass dann auch

        ${2(n+1)\choose (n+1)} < 2^{2((n+1)-1)}$

ist.

Answer 3

Hallo,

zu zeigen ist, dass$${2n\choose n}\lt 2^{2(n-1)}, \quad n \ge 5$$Der Induktionsanfang mit $n=5$ ist einfach:$${10\choose 5}=252 \lt 2^8=256 \space \checkmark$$Im Induktionsschritt soll nun gezeigt werden, dass$${2(n+1)\choose n+1} \stackrel{?}{\lt}2^{2(n+1-1)}=2^{2n}$$Bei der ersten Termumformung mache ich mir zweimal zu nutze, dass$${n \choose k} = {n-1 \choose k-1}+{n-1 \choose k}$$so dass der obere Wert des Binominalkoeffizienten zu $2n$ wird$$\begin{aligned} {2(n+1)\choose n+1}&= {2n+1\choose n} + { 2n+1 \choose n+1}\\ &= {2n\choose n-1} + 2{2n\choose n} + { 2n \choose n+1} &&(2)\\ &= 2{2n\choose n-1} + 2{2n\choose n} &&(3)\\ &= 2{2n\choose n}\cdot\frac{n}{n+1} + 2{2n\choose n}\\ &= 2{2n\choose n}\underbrace{\left( \frac{n}{n+1} + 1\right)}_{\lt 2} \\ &\lt 4 {2n\choose n} &&(6)\space \text{lt. Vorauss.}\\ &\lt 4\cdot 2^{2(n-1)} \\ &= 2^{2n} \\ &\text{q.e.d.} \end{aligned}$$zu (2): es gilt$${n \choose k} = {n \choose n-k} \implies {2n \choose n-1} = {2n \choose 2n-(n-1)} = {2n \choose n+1}$$zu (3): es gilt$${n \choose k} = {n \choose k-1} \cdot \frac{n-k+1}k \implies {n \choose k-1} = {n \choose k} \cdot \frac k{n-k+1}$$Falls noch was unklar ist, so melde Dich bitte.

Gruß Werner