How would I prove ${n^{2n} \gt (2n)!}$ using mathematical induction?

Question

This is what I have done. I checked for $n=1,2$ and $3$ in the first step. I did the assumption for $n=k$ and the claim of $n=k+1$ in the second step, but I don't understand how the step no. $3$ works so if anyone can do this a description of what you are doing in each step would be really helpful.

Answer 1

Your approach is right. But you have to note that the inequality does not hold for $n=1$ and $n=2$ respectively. Therefore your base case is given by $n=3$. You proceeded right by considering the cases $n=k$ and $n=k+1$

$$\begin{align} k^{2k}&>(2k)!\\ (k+1)^{2(k+1)}&>(2(k+1))! \end{align}$$

Now the key behind proving inequlities via induction is to somehow multiply one side of the assumption with a proper factor in order to get the claim. Form hereon you can proceed by showing that the factor which does gets the other side form assumption to claim is either smaller or bigger than the other one respectively.

So lets start with the RHS of our assumption. By using the basic property of the factorial we can conclude that we need to multiply the RHS by the factor $(2k+2)(2k+1)$ to make this side equal to $(2(k+1))!$. So lets apply this multiplication to both sides within our assumption to get

$$\begin{align} (2k)!(2k+2)(2k+1)&<k^{2k}(2k+2)(2k+1)\\ &<k^{2k}4(k+1)^2\\ &=(2k^k)^2(k+1)^2\\ &\stackrel{?}{<} \end{align}$$

The next step is a little bit tricky. To show that the RHS is actually smaller than our claimed term for the RHS, $(k+1)^{2(k+1)}$, we need to show that $2k^k<(k+1)^k$. This can be easily done by considering Bernoullis inequality for $n=k$ and $x=1/k$ respectively. Thus we get

$$1+nx< (1+x)^n\Rightarrow 1+1<\left(1+\frac1k\right)^k\Leftrightarrow 2k^k<(k+1)^k$$

Plugging the last result within our calculation so far we get

$$\begin{align} (2k)!(2k+2)(2k+1)&<k^{2k}(2k+2)(2k+1)\\ &<k^{2k}4(k+1)^2\\ &=(2k^k)^2(k+1)^2\\ &<((k+1)^k)^2(k+1)^2\\ &=(k+1)^{2(k+1)}\\ \Leftrightarrow (2(k+1))!&<(k+1)^{2(k+1)} \end{align}$$

and now we are done!

Answer 2

For $n=1$ and for $n=2$ it's wrong.

For $n\geq3$ by the assumption of the induction we obtain: $$(2n+2)!=(2n+2)(2n+1)(2n)!<(2n+2)(2n+1)n^{2n}.$$ Thus, it's enough to prove that $$(2n+2)(2n+1)n^{2n}<(n+1)^{2n+2}$$ or $$\left(1+\frac{1}{n}\right)^n>\sqrt{\frac{4n+2}{n+1}}.$$ Can you end it now?

Now, since $f(x)=\left(1+\frac{1}{x}\right)^x$ increases on $[3,+\infty)$, we obtain: $$\left(1+\frac{1}{n}\right)^n\geq\left(1+\frac{1}{3}\right)^3=\frac{64}{27}$$ and it's enough to prove that $$\frac{64}{27}>\sqrt{\frac{4n+2}{n+1}},$$ which is true because $$\frac{64}{27}>2=\sqrt{\frac{4n+4}{n+1}}>\sqrt{\frac{4n+2}{n+1}}.$$