4
$\begingroup$

I would like to prove by induction the following inequality:

$\frac{4^n}{n+1} < \binom{2n}{n}$, for all natural numbers n > 1.

Any hints?

2 Answers 2

3

You know that $\binom{2(n+1)}{n+1} = \frac{2(n+1)(2n+1)}{(n+1)^2}\binom{2n}{n}.$

The main step of the induction proof is therefore

$\frac{4^n}{n+1} \frac{2(n+1)(2n+1)}{(n+1)^2} \ge \frac{4^{n+1}}{n+2}.$

This inequality is easy to show after simplification.

  • 0
    Is there any book reference for this result? Thank you.2012-12-01
1

One has (see this question and this one) the identity $ 4^n=\sum_{i=0}^n\binom{2i}i\binom{2(n-i)}{n-i} $ On the right we have $n+1$ terms, if we can show that each one of them is at most $\binom{2n}n$, and at least one is strictly less, then we will have shown $4^n<(n+1)\binom{2n}n$. Now $\binom{2n}n$ counts the lattice paths across a $n\times n$ square, while $\binom{2i}i\binom{2(n-i)}{n-i}$ counts such paths that pass through the point $(i,i)$, so the required inequalities are obvious. I'm sorry I didn't use induction.