Prove, that for any positive integer $n \geqslant 2$ we have the inequality $$ \frac{ 4^n }{ n+1 } < \frac{ (2n)! }{ (n!)^2 }.$$

For $n=2$ the inequality is true. Directly just take and prove inequality for $k+1$ problematically. So, I think we need to find the recurrence relation to one of the members of inequality. Need some hint!


Let $a_n = \frac{4^n}{n+1}$ and $b_n=\frac{(2n)!}{n!^2}=\binom{2n}{n}$. Then $a_1=b_1$ and:

$$ \frac{a_{n+1}}{a_n} = 4 \frac{n+1}{n+2},\qquad \frac{b_{n+1}}{b_n} = 2\,\frac{2n+1}{n+1}\tag{1} $$ hence we just need to check that: $$ \forall n\geq 1,\qquad \frac{2n+2}{n+2}< \frac{2n+1}{n+1} \tag{2} $$ holds to prove our claim by induction.

Also notice that: $$\binom{2n}{n}=\sum_{j=0}^{n}\binom{n}{j}^2 > \frac{\left(\sum_{j=0}^{n}\binom{n}{j}\right)^2}{\sum_{j=0}^{n} 1}=\frac{4^n}{n+1}\tag{3}$$ follows from the Vandermonde's identity and the Cauchy-Schwarz inequality.


A simple proof is based on the observation that $\dfrac{(2n)!}{(n!)^2}$ is the central binomial coefficient $\displaystyle{ {2n} \choose n}$.

Look at row $2n$ in the Pascal triangle. The sum of all $n+1$ terms is $2^{2n}= 4^n$. Now, the central binomial coefficient is the largest number in that row and so $4^n \le (n+1){{2n} \choose n}$.

[I've used $a_1 \le M, \dots, a_k \le M$ implies $a_1+\cdots +a_{k} \le kM$.]


trivial induction:

base case $n=2$ holds. assume ${\frac{4^n}{n+1}}\lt {\frac{(2n)!}{(n!)^2}},n\ge 2$

${\frac{4^n}{n+1}}(\frac{4(n+1)}{n+2})\lt {\frac{(2n)!}{(n!)^2}}(\frac{(2n+2)(2n+1)}{(n+1)(n+1)})\space$?

${\frac{4^n}{n+1}}(\frac{4n+4}{n+2})\lt {\frac{(2n)!}{(n!)^2}}(\frac{2(n+1)(2n+1)}{(n+1)(n+1)})\space$?

${\frac{4^n}{n+1}}(2)\lt {\frac{(2n)!}{(n!)^2}}(\frac{2(2n+1)}{(n+1)})\space$?

${\frac{4^n}{n+1}}(2)\lt {\frac{(2n)!}{(n!)^2}}(\frac{4n+2}{(n+1)})\space$?

${\frac{4^n}{n+1}}(2)\lt {\frac{(2n)!}{(n!)^2}}(\frac{2n+2n+2}{(n+1)})\space$?

${\frac{4^n}{n+1}}(2)\lt {\frac{(2n)!}{(n!)^2}}({\frac{2n}{(n+1)}}+{\frac{2n+2}{(n+1)}})\space$?

($? = $not taken as true just there for simplification)

${\frac{4^n}{n+1}}(2)\lt {\frac{(2n)!}{(n!)^2}}({\frac{2n}{(n+1)}}+2),n\ge 2$

obvious that $\space 2\lt {\frac{2n}{(n+1)}}+2$ for all $n\in N$

$\therefore {\frac{4^{n+1}}{(n+1)+1}}\lt {\frac{(2(n+1))!}{((n+1)!)^2}},n\ge 2$

and it holds by Induction

  • $\begingroup$ i should have at least recognized $2n\choose n$ but oh well. $\endgroup$
    – miniparser
    Jun 29 '15 at 19:27

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.