3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Induction works fine, perhaps give it another go. $\endgroup$ – vadim123 Nov 3 '15 at 3:58
  • $\begingroup$ 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. $\endgroup$ – Laars Helenius Nov 3 '15 at 4:04
  • $\begingroup$ @SirJective: pretty sure. It's from an exam. $\endgroup$ – Arthur Nov 3 '15 at 4:05
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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,

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.