Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
12  
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
add comment

3 Answers 3

up vote 42 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|improve this answer
add comment

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|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
1  
No, I didn't miss it, that's why I wrote "in particular". –  Shai Covo Jun 22 '11 at 13:26
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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.