# Prove $n^{\ln(n)} < n!$ for $n$ big enough

I want to prove $n^{\ln(n)} < n!$ for $n$ big enough, but right now all my attempts failed...

I tried mathematical induction, but that's not working, I get stuck at showing: $$(n + 1) \cdot n^{\ln(n)} \geq (n+1)^{\ln(n+1)}$$

I thought about trying to show $\ln(n)^2 < \ln(n!) = \sum_{k=1}^n\ln(n)$ but that also got me nowhere...

Any hint would be appreciated!

First note that we can write $\log(n!)$ as

\begin{align} \log(n!)&=\sum_{k=1}^n \log(k)\\\\ &=n\log(n)+\sum_{k=1}^n\log(k/n)\tag1 \end{align}

Next, since $\log(k/n)$ is monotonically increasing, the sum on the right-hand side of $(1)$ is bounded below as

$$\sum_{k=1}^n\log(k/n)\ge \int_0^n \log(x/n)\,dx=-n \tag2$$

Putting $(1)$ and $(2)$ together reveals

$$\log(n!)\ge n(\log(n)-1) \tag 3$$

Finally, we can see that

\begin{align} \lim_{n\to \infty}\frac{\log(n!)}{\log^2(n)}&=\lim_{n\to \infty}\left(\frac{n}{\log(n)}\,\frac{\log(n)-1}{\log(n)}\right)\\\\ &=\infty \end{align}

and conclude that there exists $N$ such that for all $n>N$ we have

$$\log(n!)>\log^2(n)\implies n!>n^{\log(n)}$$

as was to be shown!

• Great proof, thank you! – Jonny Nov 8 '16 at 3:53
• You're welcome! My pleasure. -Mark – Mark Viola Nov 8 '16 at 3:54

Take the logarithm, as per your second idea.

$$\ln (n^{\ln n}) = \ln^2 n$$ while $$\ln n! = \sum_{k=1}^n \ln k > \sum_{k=\lfloor n/2\rfloor}^n \ln k \geq \frac{n}{3}\ln \frac{n}{3} = \frac{1}{3}n\ln n - \frac{\ln 3}{3}n > \frac{1}{4} n\ln n$$ for $n$ large enough. Can you conclude?

• Thanks, @Clement. $c \cdot n > \ln(n)$ with $c > 0$ is true for $n$ big enough, hence: $\frac{1}{4} \cdot n \cdot \ln(n) > \ln(n) \cdot \ln(n) = \ln(n)^2 = \ln(n^{\ln(n)})$, great! Do you know another proof to show the inequality? I like looking at those things from different angles. – Jonny Nov 7 '16 at 22:50
• You could look at Stirling's formula, for instance (it's a heavier hammer). – Clement C. Nov 7 '16 at 22:51
• See also math.stackexchange.com/a/1671964/589. – lhf Nov 8 '16 at 0:12

Induction is working, too by the way...

We are using $n + 1 < 2n$ to prove $(n + 1)^{\ln(n+1)} < (n+1)!$ for $n$ big enough as the inductive step.

$$(n + 1)^{\ln(n+1)} < (2n)^{\ln(n+1)} = 2^{\ln(n+1)} \cdot n^{\ln(n+1)} = (n+1)^{\ln(2)} \cdot n^{\ln(n+1)}$$ $$< (2n)^{\ln(2)} \cdot n^{\ln(n+1)} = 2^{\ln(2)} \cdot n^{\ln(2)} \cdot n^{\ln(n+1)}$$ $$= 2^{\ln(2)} \cdot n^{\ln(2)} \cdot n^{\ln(n)} \cdot n^{\ln(n+1) - \ln(n)} \overset{\text{inductive basis}}{<} n! \cdot 2^{\ln(2)} \cdot n^{\ln(2)} \cdot n^{\ln(n+1) - \ln(n)}$$ $$= n! \cdot 2^{\ln(2)} \cdot n^{\ln(2 + \frac{2}{n})} \overset{\ln(2) < 1}{<} n! \cdot (n+1) = (n+1)!$$

• Very clever. Induction did work after all. – DanielWainfleet Nov 8 '16 at 21:16

Pick some $N$ such that for all $n >N$ we have: $$\frac{n}{2} \geq \sqrt{n}$$ and $$\frac{n}{4}-\frac{1}{2} \geq \log(n)$$

Then

$$n! \geq (\lfloor \frac{n}{2} \rfloor+1)(\lfloor\frac{n}{2}\rfloor+2)...n \\\geq \left( \frac{n}{2} \right)^{\frac{n}{2}-1} \geq \left( \sqrt{n} \right)^{\frac{n}{2}-1} = n^{{\frac{n}{4}-\frac{1}{2}}} \geq n^{\log(n)}$$

• Great proof! Thanks! – Jonny Nov 8 '16 at 21:01