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^8 =  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