Proving $\binom{2n}{n} \geq \frac{2^{2n}}{n+1}$ How can I prove this?
$$\binom{2n}{n} \geq \frac{2^{2n}}{n+1}$$
I tried using AM-GM but it didn't help.
 A: You may use induction:
$$
\binom{2n}{n} = \binom{2n-2}{n-1}\frac{{(2n)(2n - 1)}}{{n^2 }} \ge \frac{{2^{2n - 2} }}{n}\frac{{(2n)(2n - 1)}}{{n^2 }} \\ = \frac{{2^{2n} }}{{n + 1}}\left( {1 + \frac{1}{{2n}} - \frac{1}{{2n^2 }}} \right) \ge \frac{{2^{2n} }}{{n + 1}}.
$$
A: This smells like induction to me...
First, let's rewrite this inequality as
$${(2n)!\over (n!)^2}\geq {2^{2n}\over n+1}$$
This inequality is true for $n=0$, which will be our base case. Now suppose this inequality is true for an arbitrary $n$. Then, consider the $n+1$ case.
$$\frac{(2n+2)!}{((n+1)!)^2}=\frac{(2n)!}{(n!)^2}\times\frac{(2n+2)(2n+1)}{(n+1)^2}=\frac{(2n)!}{(n!)^2}\times\frac{2(2n+1)}{n+1}$$
$$\frac{2^{2n+2}}{n+2}=\frac{2^{2n}}{n+1}\times\frac{4(n+1)}{n+2}$$
Notice that
$$\frac{2(2n+1)}{n+1}\geq\frac{4(n+1)}{n+2}$$
Because
$$(4n+2)(n+2)\geq 4(n+1)^2$$
$$4n^2+10n+4\geq 4n^2+8n+4$$
for all $n\geq 0$. So, since $\frac{(2n)!}{(n!)^2}\geq\frac{2^{2n}}{n+1}$ and $\frac{2(2n+1)}{n+1}\geq\frac{4(n+1)}{n+2}$, then the inductive step holds, i.e.
$$\frac{(2n+2)!}{((n+1)!)^2}\geq\frac{2^{2n+2}}{n+2}$$
This completes the proof by induction.
A: The LHS of the inequality has the recurrence relation: $$\binom{2n}{n} = \binom{2(n-1)}{n-1} \left(4-\frac{2}{n}\right)$$
The RHS has the recurrence relation: $$\frac{2^{2n}}{n+1} = \frac{2^{2(n-1)}}{(n-1)+1} * \frac{4n}{n+1}$$
Then it is easy to prove by induction. Clearly, the inequality is true in the base case of $n = 1$. Then it is sufficient to show that $$4-\frac{2}{n} \ge \frac{4n}{n+1}$$ for $n \ge 1$. This is $$4-\frac{2}{n} \ge 4 - \frac{4}{n+1} \to \frac{2}{n} \le \frac{4}{n+1}$$
Cross-multiplying yields $$2(n+1) \le 4n \to 1 \le n$$, the original condition. Because the LHS is increasing at a faster rate than the RHS, the inequality is true for all $n \ge 1$.
