# How can I prove this inequality for $n\geq 2$?

How can I prove this inequality for all natural numbers $n\geq 2$?

${2n\choose n}>\frac{4^n}{n+1}$

I've tried induction but that was a dead end.

• Induction works fine, perhaps give it another go. – vadim123 Nov 3 '15 at 3:58
• Well $\binom{2n}{n}\sim\frac{2^{2n}}{\sqrt{\pi n}}>\frac{4^n}{n+1}$, so for large enough $n$ it seems to be true. – Laars Helenius Nov 3 '15 at 4:04
• @SirJective: pretty sure. It's from an exam. – Arthur Nov 3 '15 at 4:05

For $n=2$, $${4\choose 2}=6> \frac{16}{3}$$

Assume $${{2k}\choose{k}}>\frac{4^k}{k+1}$$

Then $${{2k+2}\choose {k+1}}=\frac{(2k+2)(2k+1)}{(k+1)}{{2k}\choose k}$$

$$>\frac{(2k+2)(2k+1)}{(k+1)}\frac{4^k}{k+1}$$

$$={2(2k+1)}\frac{4^k}{k+1}$$

$$=4k\frac{4^k}{k+1}+2\frac{4^k}{k+1}$$

$$>4\frac{4^k}{k+1}$$

$$=\frac{4^{k+1}}{k+1}$$

$$>\frac{4^{k+1}}{k+2}$$

Hopefully I didnt mess up the algebra but the idea is right.

Induction actually does work. Let $a_n$ denote the LHS and $b_n$ denote the RHS at the $n^{\text{th}}$ step. Then $$\frac{a_n}{a_{n-1}} = \frac{2n(2n-1)}{n^2} = \frac{4n-2}n, \quad \frac{b_n}{b_{n-1}} = \frac{4n}{n+1}.$$ To figure out which factor is bigger, we consider their ratio : $$\frac{\frac{4n-2}{n} }{ \frac{4n}{n+1}} = \frac{(4n-2)(n+1)}{4n^2} = \frac{4n^2+2n-2}{4n^2} \ge 1$$ as long as $2n-2 \ge 0$, i.e. as long as $n \ge 1$. So you can start induction at $n=2$ where $\binom{2n}n = \binom 42 = 6 > \frac{16}3 = \frac{4^2}{2+1}$.

Hope that helps,