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

Question

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!

Answer 1

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?

Answer 2

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!

Answer 3

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

Answer 4

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