Show $\left( n!\right)^2 > n^n$. [duplicate]

Question

If $n > 2$, show that $$\left(n!\right)^2 > n^n$$

Although the problem is pretty obvious, I couldn't come up with a rigorous proof. I was thinking some sort of AM-GM, but couldn't build anything concrete.

I have a feeling this problem could be a duplicate, I tried to google, and even searched on the stackexchange network, couldn't find it.

Answer 1

We do the induction step. If $(k!)^2\gt k^k$, and $k\ge 3$, we show that $((k+1)!)^2 \gt (k+1)^{k+1}$, Note that $((k+1)!)^2 =(k+1)^2(k!)^2 = (k+1)^2(k!)^2 \gt (k+1)^2 k^k$.

We show that $(k+1)^2 k^k \gt (k+1)^{k+1}$, or equivalently that $(k+1)k^k \gt (k+1)^k$. So we need to show that $k+1 \gt \left(1+\frac{1}{k}\right)^k$. This is true, since $\left(1+\frac{1}{k}\right)^k \lt e$.

Another way: Note that $(n!)^2 =\prod_1^n k(n+1-k)$. The function $x(n+1-x)$ increases until $x=\frac{n+1}{2}$, then decreases. In particular, $k(n+1-k)\ge (1)(n)=n$. So the product $\prod_1^n k(n+1-k)$ is $\ge$ the product of $n$ copies of $n$.

Answer 2

Base case, $n=3$, is true by $(3!)^2 = 36 > 27 = 3^3$.

Suppose that we have for $k>2$, $(k!)^2 > k^k$ (IH), now we want to show that $((k+1)!)^2 > (k+1)^{k+1}$.

\begin{align*} ((k+1)!)^2 &= ((k+1)(k!))^2\\ &=(k+1)^2(k!)^2>(k+1)^2k^k \qquad\text{ (where the inequality is from IH)} \end{align*}

So if we can show that $(k+1)^2k^k>(k+1)^{k+1}$ then we are done. I'll leave that up to you.

Answer 3

$$ n\ge k\ge 1\implies n(k-1)\ge k^2-k\implies nk-k^2+k\ge n \\ \implies n-k+1\ge \frac nk $$

Now make the product of these inequalities for $1\le k \le n$: $$n! = (n-1+1)(n-2+1)\cdots (n-n+1) \ge \frac {n^n}{n!} $$

The macroscopic inequality is strict as soon as it is strict for one microscopic inequality, that is when there is $k$ such as $1<k<n$, ie $n>2$.

Answer 4

It's easy to see that

$${n\choose k}\left({1\over n}\right)^k\lt{n\over n}\cdot{n-1\over n}\cdot\cdots\cdot{n-k+1\over n}\lt1$$

if $n\ge2$ and hence

$$\left(1+{1\over n}\right)^n=\sum_{k=0}^n{n\choose k}\left({1\over n}\right)^k\lt\sum_{k=0}^n1=n+1$$

It now follows that

$$(n+1)^{n+1}=(n+1)\left(1+{1\over n}\right)^nn^n\lt(n+1)^2n^n\le(n+1)^2(n!)^2=((n+1)!)^2$$

using induction (and the base case $2^2=(2!)^2$) for the final inequality.