Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 45 down vote accepted

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 $$

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.