0
$\begingroup$

I am stuck at the following exercise:

Show that for $n \rightarrow \infty$ holds

$$\log(n!) = n \log n − n + \mathcal{O}(\log n).$$

I do not see how I should prove this. I know that

$$\log(n!) = \log(n)+\log(n-1)+\cdots+\log(1)$$

, and I see that this is similar to $$n\log(n) = \sum_{i=1}^n \log(n)$$but I do not see how this should help here. Could you give me a hint?

$\endgroup$
  • 2
    $\begingroup$ Use estimates on the error of a Riemann sum approximation. $\endgroup$ – MathematicsStudent1122 Jun 17 at 18:44
1
$\begingroup$

Let us treat this as an exercise in summation by parts:

$$ \log(N!)=\sum_{n=1}^{N}\log(n)=N\log N-\sum_{n=1}^{N-1}n\log\left(1+\frac{1}{n}\right) $$ and by Maclaurin series $\log(1+x)=x-\frac{x^2}{2}+O(x^3)$, so $$ \log(N!)=N\log N-(N-1)+\sum_{n=1}^{N-1}n\left(\frac{1}{n}-\log\left(1+\frac{1}{n}\right)\right)$$ equals $$ N\log N-N+1+\sum_{n=1}^{N-1}\left(\frac{1}{2n}+O\left(\frac{1}{n^2}\right)\right) $$ i.e. $$ N\log N - N + \frac{1}{2}\log N + O(1). $$ Probably the hardest part of the proof of Stirling's inequality is to show that the last $O(1)$ term hides $\frac{1}{2}\log(2\pi)+O\left(\frac{1}{n}\right)$, but this weaker form is usually more than enough for concrete applications.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

$$\int_{1}^{n} \log x dx < \log n! = \sum_{k=1}^{n} \log k < \int_{1}^{n+1}\log x dx $$ Can you solve for these integrals?

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

$\sum_{i=1}^n \log(i)$ is a left hand Riemann sum for $\int_1^{n+1} \log(x) dx$. It is also a right hand sum for $\int_0^n \log(x) dx$.

Now $\log$ is an increasing function, so its right hand sums are bigger than its integrals and its left hand sums are smaller than its integrals, so your sum lies between these two numbers, and the difference between these two numbers turns out to be $O(\log(n))$ as $n \to \infty$ (which you should show yourself).

One can make one of the bounds slightly better by noticing that $\sum_{i=1}^n \log(i) = \sum_{i=2}^n \log(i)$ since $\log(1)=0$. This sum starting at $2$ is now a right hand sum for $\int_1^n \log(x) dx$. For this particular exercise, either way will suffice.

| cite | improve this answer | |
$\endgroup$

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.