# Problem proving inequality (4^n)/(n+1)<=((2n)!)/((n!)^2) I skip the base case n=0 because it's obvious. I know that this is very equivalent to: Prove by induction: (2^(2n))/(n+1)<((2n)!)/((n!)^2),n>1

Problem proving inequality $\frac{{4}^{n}}{n+1}\le \frac{\left(2n\right)!}{\left(n!{\right)}^{2}}$
I skip the base case $n=0$ because it's obvious.
I know that this is very equivalent to: Prove by induction: $\frac{{2}^{2n}}{n+1}<\frac{\left(2n\right)!}{\left(n!{\right)}^{2}},n>1$
But I try to learn some tricks so maybe you can help me?
Assumption: $\frac{{4}^{n}}{n+1}\le \frac{\left(2n\right)!}{\left(n!{\right)}^{2}}\phantom{\rule{thickmathspace}{0ex}}⟺\phantom{\rule{thickmathspace}{0ex}}{4}^{n}\le \frac{\left(n+1\right)\left(2n\right)!}{\left(n!{\right)}^{2}}$ for some n.
Step: $n\to n+1$
${4}^{n+1}=\frac{\left(n+2\right)\left(2n+2\right)!}{\left(\left(n+1\right)!{\right)}^{2}}$
I begin with manipulating the LHS:
${4}^{n+1}=4\cdot {4}^{n}\le ???$
$???\le \frac{\left(2n\right)!\left(2n+2\right)\left(2n+1\right)\left(n+1\right)}{\left(n!\left(n+1\right)\right)}$
$=\frac{\left(n+1\right)\left(2n+2\right)!}{\left(\left(n+1\right)!{\right)}^{2}}$
Note that I want to work my way from both sides to the mid where I get a very easy to check inequality by assumption.
Can you help me?
You can still ask an expert for help

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

scranna0o
$\frac{{4}^{n+1}}{\left(n+2\right)}<\frac{\left(2n\right)!}{\left(n!{\right)}^{2}}\frac{4\left(n+1\right)}{\left(n+2\right)}$
Now
$\frac{\left(2n\right)!}{\left(n!{\right)}^{2}}\frac{4\left(n+1\right)}{\left(n+2\right)}=\frac{\left(2n+2\right)!}{\left(\left(n+1\right)!{\right)}^{2}}\frac{4\left(n+1{\right)}^{3}}{\left(n+2\right)\left(2n+1\right)\left(2n+2\right)}$
So
$\frac{4\left(n+1{\right)}^{3}}{\left(n+2\right)\left(2n+1\right)\left(2n+2\right)}<1$
implies
$\frac{\left(2n+2\right)!}{\left(\left(n+1\right)!{\right)}^{2}}\frac{4\left(n+1{\right)}^{3}}{\left(n+2\right)\left(2n+1\right)\left(2n+2\right)}<\frac{\left(2n+2\right)!}{\left(\left(n+1\right)!{\right)}^{2}}$
, for $n>1$