5
$\begingroup$

I need to prove that $n \ln(n) - n \le \ln(n!)$. I have solved this but I've used the Stirling substitution for the factorial term which does not seem good to me in this proof. I am sure that there must be a direct way to solve this.
One way I can think about tackling this problem is simply breaking the left and right hand side into primary terms:
$$\ln(n!) = \ln(n) + \ln(n-1) + \ln(n-2) + \dots + \ln(2) + \ln(1)$$ $$n \ln(n) - n = n (\ln(n)-1) = (\ln(n) - 1) + (\ln(n) -1) + \dots + (\ln(n) -1)$$
I need to somehow show that the the top expression is greater than the bottom expression, but I can only be sure that $\ln(n) > \ln(n) -1$ and that $ \ln(n-1)>\ln(n) - 1$
What can I do about the rest?

$\endgroup$
3
  • $\begingroup$ $\ln(n)-n$ is negative! Do you mean $n-\ln(n)$? $\endgroup$
    – OmG
    Mar 7, 2018 at 21:45
  • $\begingroup$ @OmG, I meant $n ln(n) - n$. Thank you for correction. $\endgroup$
    – Aemilius
    Mar 7, 2018 at 21:47
  • $\begingroup$ @BarryCipra I have corrected that in text, Too. Thank you for letting me know! $\endgroup$
    – Aemilius
    Mar 7, 2018 at 21:49

3 Answers 3

10
$\begingroup$

Recall that the sequence $$ e_n = \left( 1+ \frac 1n \right)^n $$ is increasing and converges to $e$. Thus, $$ e^n \ge e_1 \cdot e_2 \cdot \ldots \cdot e_n = \frac{(n+1)^n}{n!}. $$ In particular we obtain the weaker inequality $e^n \ge \frac{n^n}{n!}$, which is equivalent to $n \ln n - n \le \ln (n!)$.


A by-product of this is that the sequence $$ \sqrt[n]{e_1 \cdot e_2 \cdot \ldots \cdot e_n} = \frac{n+1}{\sqrt[n]{n!}} $$ is increasing and tends to $e$ (by an application of Stolz-Cesaro theorem).

$\endgroup$
1
  • $\begingroup$ very nice, I used a similar idea by induction but this is more elegant! $\endgroup$
    – user
    Mar 7, 2018 at 22:14
9
$\begingroup$

As an alternative note that

$$ n \ln n - n \le \ln(n!)\iff e^{n \ln n - n}\le e^{\ln(n!)}\iff \frac{n^n}{e^n}\le n!$$

which can be proved by induction as follow

base case

  • $n=1 \implies \frac1e \le 1$

induction step

  • assume $\frac{n^n}{e^n}\le n!$

  • $\frac{(n+1)^{n+1}}{e^{n+1}}=\frac{n+1}{e}\frac{(n+1)^n}{n^n}\frac{n^n}{e^n}\le \frac{n+1}{e}\left(1+\frac1n\right)^n n!\le(n+1)n!=(n+1)!$

$\endgroup$
6
$\begingroup$

$$ n \log n - n +1 = \int_1^n \; \; \log x \; \; dx < \sum_{j = 2}^n \log j \; = \log n! $$

diagram for $n=4$

enter image description here

$\endgroup$
1
  • $\begingroup$ Actually $n \log n - n \color{red}{+1} = \int_1^n \; \; \log x \; \; dx$, giving a slightly sharper result. $\endgroup$
    – Martin R
    Nov 25, 2019 at 12:23

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.