20
$\begingroup$

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

  • 13
    The 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 3

45

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 $

12

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!}}. $

  • 1
    No, I didn't miss it, that's why I wrote "in particular".2011-06-22
11

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