<s>[INST] 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.
 [/INST] 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.
</s>