Prove that $(n!)^2$ is greater than $n^n$ for all values of n greater than 2.

Question

This problem , I assume can be proved using induction, however I am trying to find another way.

Is there a simple combinatorial approach? One notices that $(n!)^2$ is equal to the number of permutations of size n squared, and that $n^n$ is the number of redundant combinations where there are n spaces and n choices.

Any help would be much appreciated.

Thanks

Answer 1

This is not combinatorial, but note that $$(n!)^2=\prod_{k=1}^n k(n+1-k).$$ (We are in essence using the "Baby Gauss" trick.) But if $k$ is not $1$ or $n$, we have $k(n+1-k)\gt n$.

Answer 2

divide $(n!)^2 > n^n$ by $n!$ to get

$$n! = 1 \times 2 \times \ldots \times (n-1) \times n > \frac{n}{n} \times \frac{n}{n-1} \times \ldots \times \frac{n}{2} \times \frac{n}{1}$$

It is a bit of simple algebraic manipulation to show that each term on the lhs is greater or equal to the corresponding term on the rhs, or $\frac{n}{n-k} < k+1 $ for $k \in \overline{0, n-1}$