Prove that for $n \ge 2$ the follow inequality holds $\frac {4^n}{n+1} \lt \frac{(2n)!}{(n!)^2}$.

Question

As already shown above I need to prove that $$\frac {4^n}{n+1} \lt \frac{(2n)!}{(n!)^2}\qquad \forall n \ge 2.$$

What I've come up with is the following:

$\underline{n=2:}\qquad$ $$\frac {16}{3} \lt 6$$

$\underline{n=k:}\qquad $$$\frac {4^k}{k+1} \lt \frac{(2k)!}{(k!)^2} $$

$\underline{n+1}:$ $$\frac {4^{k+1}}{k+2} \lt \frac{(2(k+1))!}{((k+1)!)^2} $$ $$\frac{4^k \cdot 4}{k+2} \lt \frac {(2k+2)!}{(k!)^2\cdot(k+1)\cdot(k+1)}$$ $$\frac{4^k \cdot 4}{k+2} \lt \frac{(k+1)\cdot \ldots \cdot (k + (k-1))\cdot{2k} \cdot (2k+1)\cdot(2k+2)}{(k!)^\require{enclose}\enclose{updiagonalstrike}2\cdot(k+1)\cdot(k+1)}$$ $$\frac{4^k \cdot 4}{k+2} \lt 2 \cdot\frac{\require{enclose}\enclose{updiagonalstrike}{(k+1)}\cdot \ldots \cdot (k + (k-1))\cdot{2k} \cdot (2k+1)\cdot\require{enclose}\enclose{updiagonalstrike}{(k+1)}}{(k!)\cdot\require{enclose}\enclose{updiagonalstrike}{(k+1)}\cdot\require{enclose}\enclose{updiagonalstrike}{(k+1)}}$$ $$\frac{4^k \cdot 4}{k+2} \lt 2 \cdot\frac{{(k+2)}\cdot \ldots \cdot (k + (k-1))\cdot{2k} \cdot (2k+1)}{(k!)}$$

From here on I'm stuck. Can somebody help me please?

Answer 1

For $k+1$ it is equivalent to

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

It is enough to prove that

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

Notice that the above fraction is monotonically decreasing and its limit at $k\to\infty$ is $1$, therefore it is always greater than $1$.

And also, you have a mistake, as Harry noticed, $(2k)!\neq2k!$.

Edit

I have no idea what is Jaroslaw talking about. There is step-by-step solution. Suppose it is true for $k$. Then it is true for $k+1$ if and only if

$$\frac{4^{k+1}}{k+2}<\frac{(2k+2)!}{\left((k+1)!\right)^2}\\\frac{4^k}{k+1}\cdot\frac{4(k+1)}{k+2}<\frac{(2k+2)(2k+1)(2k)!}{(k+1)^2(k!)^2}\\\frac{4^k}{k+1}\cdot\frac{4(k+1)}{k+2}<\frac{(2k)!}{(k!)^2}\cdot\frac{(2k+2)(2k+1)}{(k+1)^2}$$

It is enough to prove that:

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

It is equivalent to

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

Answer 2

Note that $$\frac{\frac{4^{n+1}}{n+2}}{\frac{4^n}{n+1}}=4\frac{n+1}{n+2}$$ and that $$\frac{\frac{(2(n+1))!}{(n+1)!^2}}{\frac{(2n)!}{n!^2}}=\frac{(2n+2)!}{(2n)!}\cdot\frac{n!^2}{(n+1)!^2}=\frac{(2n+2)(2n+1)}{(n+1)^2}=2\frac{2n+1}{n+1}. $$So, when is it true that$$4\frac{n+1}{n+2}\leqslant2\frac{2n+1}{n+1}?$$ Well, the previous inequaliy is equivalent to $2(n+1)^2\leqslant(2n+1)(n+2)=2n^2+5n+2$, which clearly holds always. So, since you proved that $\frac{4^2}{2+1}<\frac{(2\times2)!}{2!^2}$, the inequality that you want to prove is true whenever $n\geqslant2$.

Answer 3

As your first steps of mathematical induction are right, I'll just perform a proof of inductive thesis for $n=k+1$.

First notice, that for $k>1$ $$\frac{4(k+1)}{(k+2)} < \frac{(2k+2)(2k+1)}{(k+1)^2}$$ proof: $$(k-1)k(k+1)^2(k+2)>0\\ \frac{k(k-1)}{(k+1)^2(k+2)}>0\\ \frac{4k^2-4k}{(k+1)^2(k+2)}>0\\ \frac{-4k^2+4k}{(k+1)^2(k+2)}<0\\ \frac{4(k^3+3k^2+3k+1)-(4k^3+16k^2+8k+4)}{(k+1)^2(k+2)}<0\\ \frac{4(k+1)^3}{(k+1)^2(k+2)}<\frac{4k^3+16k^2+8k+4}{(k+1)^2(k+2)}\\ \frac{4(k+1)^2}{(k+1)^2(k+2)}<\frac{(2k+2)(2k+1)(k+2)}{(k+1)^2(k+2)}\\ \frac{4(k+1)}{(k+2)}<\frac{(2k+2)(2k+1)}{(k+1)^2}$$

Thus, since $\frac{4(k+1)}{(k+2)}$ and $\frac{4^k}{k+1}$ are both positive, we have: $$\frac{4^{k+1}}{k+2}=\frac{4(k+1)}{(k+2)}\frac{4^k}{k+1} < \frac{4(k+1)}{(k+2)}\frac{(2k)!}{(k!)^2}<\frac{(2k+2)(2k+1)}{(k+1)^2}\frac{(2k)!}{(k!)^2} = \frac{(2k+2)!}{(((k+1)!)^2}$$