# How do you prove that $n^n$ is $O(n!^2)$?

It seems obvious that: $$n^n \in O(n!^2)$$ But I can't seem to find a good way to prove it.

-
The lazy person's solution would be to invoke Stirling's approximation, but as the two answers indicate, there are much better ways to see it. You should learn about Stirling, though, it's as useful as it is beautiful. – t.b. Jun 22 '11 at 12:38

## 3 Answers

Use a multiplicative variant of Gauss's trick: $$(n!)^2 = (1 \cdot n) (2 \cdot (n-1)) (3 \cdot (n-2)) \cdots ((n-2) \cdot 3) ((n-1) \cdot 2) (n \cdot 1) \ge n^n$$

-

Group factors $k$ and $n-k$. When is their product bigger than $n$?

-

This also follows straightforwardly from the simple inequality $$e\bigg(\frac{n}{e}\bigg)^n \le n!,$$ which can be found here (Wikipedia).

Elaborating: From this inequality it follows in particular that $$n!n! \ge \frac{{n^n n^n }}{{e^n e^n }} = \bigg(\frac{n}{{e^2 }}\bigg)^n n^n ,$$ hence $$n^n \le \bigg(\frac{{e^2 }}{n}\bigg)^n n!n!,$$ showing moreover that $n^n \in o(n!^2)$.

EDIT: Here (Math Central, Problem of the Month 100, December 2010) you can find five different proofs of the inequality $(n!)^2 > n^n$, for all $n \geq 3$ or $n \geq 8$.

EDIT: Actually, for the above proof it suffices to use the inequality $n! > (\frac{n}{e})^n$ (cf. the comments below), which is trivial noting that $$e^n = \sum\limits_{k = 0}^\infty {\frac{{n^k }}{{k!}}} > \frac{{n^n }}{{n!}}.$$

-
Thanks! But I think you missed a factor $e^2$ in the second part of your answer, not that this changes anything. – Guillaume Martres Jun 22 '11 at 13:16
No, I didn't miss it, that's why I wrote "in particular". – Shai Covo Jun 22 '11 at 13:26