It seems obvious that: $n^n \in O(n!^2)$ But I can't seem to find a good way to prove it.
How do you prove that $n^n$ is $O(n!^2)$?
-
13The lazy person's solution would be to invoke [Stirling's approximation](http://en.wikipedia.org/wiki/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. – 2011-06-22
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 $
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!}}. $
-
1No, I didn't miss it, that's why I wrote "in particular". – 2011-06-22
Group factors $k$ and $n-k$. When is their product bigger than $n$?