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.

$\endgroup$
  • 13
    $\begingroup$ 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. $\endgroup$ – t.b. Jun 22 '11 at 12:38
45
$\begingroup$

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

$\endgroup$
12
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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