Vollständige Induktion. Ungleichung mit Binomialkoeffizient zeigen

Question

Kann mir jemand diesen Schritt (zweite Zeile) erklären?

\( \left(\begin{array}{c}2 n+2 \\ n+1\end{array}\right) = \frac{(2 n+2) !}{(n+1) ! \cdot(n+1) !} \\ = \frac{(2 n) !}{n ! \cdot n !} \cdot \frac{(2 n+1)(2 n+2)}{(n+1)^{2}} > 2^{n} \cdot 2 \cdot \frac{2 n+1}{n+1} \\ >2^{n+1} \)

Ich weiß nicht, warum die linke Seite jetzt größer sein soll als die rechte.

Answer 1

Das muss an der Induktionsvoraussetzung liegen.

Wie lautet die denn genau?

Comments

Die Induktionsvoraussetzung lautet

\( \left(\begin{array}{c}2 n \\ n\end{array}\right)>2^{n} \)

---

( 2n tief n) = (2n)! / ( n! * n!)  < 2^n wurde eingesetzt

Answer 2

Hi,
$$ \frac{(2n)!}{n! \cdot n!} \frac{(2n+1)(2n+2)}{(n+1)^2} = 2 \cdot \frac{2n+1}{n+1} \frac{(2n)!}{n! \cdot n!}  $$
Es gilt
$$ \frac{(2n)!}{n! \cdot n!} = \frac{ 2n \cdot (2n-1) \cdots (n+1) }{ n \cdot (n-1) \cdots 1 } = \prod_{k=0}^{n-1} \frac{2n-k}{n-k} $$
weiter gilt $$ \frac{2n - k}{n-k} > 2  $$ für \( 0 < k < n \)
also die behauptete Ungleichung. Allerdings für \( n = 1 \) gilt die Ungleichung nicht, weil
$$ \frac{2!}{1! \cdot 1!} \frac{3 \cdot 4}{4} = 6  $$ gilt und
$$ 2^1 \cdot 2 \cdot \frac{3}{2}  = 6 $$ gilt.

Comments

Wieso ist

\( \frac{(2 n) !}{n ! \cdot n !} \frac{(2 n+1)(2 n+2)}{(n+1)^{2}}=2 \cdot \frac{2 n+1}{n+1} \frac{(2 n) !}{n ! \cdot n !} \)

Ich kann das einfach nicht sehen.

---

Das gilt, weil \( (2n + 2) = 2(n+1) \) gilt. Und dann kann man den Faktor \( n+1 \) kürzen.