3
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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!

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

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jonny Nov 7 '16 at 22:50
  • $\begingroup$ You could look at Stirling's formula, for instance (it's a heavier hammer). $\endgroup$ – Clement C. Nov 7 '16 at 22:51
  • $\begingroup$ See also math.stackexchange.com/a/1671964/589. $\endgroup$ – lhf Nov 8 '16 at 0:12
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Very clever. Induction did work after all. $\endgroup$ – DanielWainfleet Nov 8 '16 at 21:16
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Great proof! Thanks! $\endgroup$ – Jonny Nov 8 '16 at 21:01

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.