How to solve the inequality $n! \le n^{n-2}$?

Question

The inequality is $n! \le n^{n-2}$. I used Stirling's approximation for factorials and my answer was $n \le (e(2\pi)^{-1/2})^{2/5}$ but this doesn't seem right. Any help would be much appreciated.

Answer 1

Here's an elementary proof, with some details left out to be filled in by you :).

Taking logarithms, you want to show that $$ S_n = \log 2 + \log 3 + \dots \log n \le (n-2) \log n \, . $$ Note that there are $n-1$ terms on the left, each less than $\log n$. So you only have to "squeeze out" an additional term $\log n$. This can be done as follows:

Let $k = \lfloor \sqrt{n} \rfloor$, that is, $k$ is the largest integer such that $k \le \sqrt{n} < k+1$. Split the sum on the left to obtain: $$ \log 2 + \log 3 + \dots + \log k + \log (k+1) + \dots + \log n $$ The terms up to $\log k$ are all $\le \log \sqrt{n} = \frac{1}{2} \log n$, and there are $k-1$ such terms. The remaining terms are all $\le \log k$, and there are $n-k$ such terms.

Add everything up. The result is $$ S_n \le (k-1) \frac{\log n}{2} + (n-k) \log n = \left( n - \frac{k + 1}{2} \right) \log n . $$ Now determine for which $k$ and therefore for which $n$ this implies $S_n \le (n-2) \log n$. You'll notice that you have proved the inequality for $n \ge 9$ or so. As Robert Israel already pointed out, the inequality actually holds for $n \ge 5$. These remaining cases can be checked by direct computation.

Answer 2

Stirling says $n! \approx \sqrt{2\pi} n^{n-1/2} e^{-n}$. Let $S(n)$ be the right side of that. Now $S(n) \le n^{n-2}$ is equivalent to $\sqrt{2\pi} n^{5/2} \le e^n$, and that's certainly true for large enough $n$ (an exponential always beats a power in the end). To find exactly what $n$ makes the two equal requires using the Lambert W function: it turns out to be $$-\frac{5}{2}\,{\it W} \left( -1,-{\frac {{2}^{4/5}}{5\; {\pi^{1/5} }}} \right) \approx 4.883692535 $$ Of course this is only for the approximation, not the actual $n!$. But in fact your inequality $n! \le n^{n-2}$ is true for $n \ge 5$ (note that $4! > 4^2$ and $5! < 5^3$).

Answer 3

Here's a proof by induction.

First, we need to verify the base case: $5!=120 < 125=5^3$

Now assume the induction hypothesis $n! < n^{n-2}$ is true, then we need to prove $$(n+1)! < (n+1)^{n-1} \Leftrightarrow n! < (n+1)^{n-2}.$$

But by induction hypothesis and the fact $n < n+1$ we have, $$n! < n^{n-2} < (n+1)^{n-2}.$$

Therefore $(n+1)! < (n+1)^{n-1}$ and we are done.