Some trouble with the induction

Question

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!

Answer 1

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.

Answer 2

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

Answer 3

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$.]