A question on the Stirling approximation, and $\log(n!)$

In the analysis of an algorithm this statement has come up:$$\sum_{k = 1}^n\log(k) \in \Theta(n\log(n))$$ and I am having trouble justifying it. I wrote $$\sum_{k = 1}^n\log(k) = \log(n!), \ \ n\log(n) = \log(n^n)$$ and it is easy to see that $\log(n!) \in O(\log(n^n))$, but the "$\Theta$" part is still perplexing. I tried calculating the limit: $$\lim_{n \to\infty} \frac{\log(n!)}{\log(n^n)}$$but the only way that I thought of doing this was to substitute the Stirling approximation in the numerator, and it works, but this would only be justified if $$\lim_{n \to\infty}\frac{\log(n!)}{\log(\sigma(n))} = 1$$(with $\sigma(n) = \sqrt{2\pi} \cdot n^{\frac{1}{2} + n} \cdot e^{-n} $) and is it? It is certainly wrong that $$a_n \sim b_n \ \Rightarrow \ f(a_n) \in \Theta(f(b_n))$$ for a general (continuous) $f : \mathbb{R} \rightarrow \mathbb{R}$, since, for example, $a_n =n^2+n, b_n=n^2$ and $f(x) = e^x$ is a counterexample (since $\frac{n^2 + n}{n^2} \rightarrow 1$, but $ \frac{e^{n^2+n}}{e^{n^2}} \rightarrow +\infty$). So here are my questions:

1. Is the statement true under certain hypothesis on $f$ (for example $f \in O(x)$ would be plausible), and in particular in the case of the $f(x) = \log(x)$?
2. If not, how can I proceed in the initial proof, using Stirling, or otherwise?

I do not know (and don't want to use) anything andvanced on the Stirling approximation, such as error estimates; I know that $n! = \sigma(n)(1+ O(\frac{1}{n}))$, and not much more.

Any help is appreciated. Thank you.

Solution 1:

Here's another answer to question 2. By the Stolz–Cesàro theorem,

$$\lim_{n\to\infty}\frac{\log(n!)}{\log(n^n)}=\lim_{n\to\infty}\frac{\log(n+1)}{\log(n+1)+\log\left(\left(1+\frac{1}{n}\right)^n\right)}=1.$$

For a partial answer to question 1, here's a way to see that $a_n\sim b_n$ implies $\log(a_n)\sim\log(b_n)$ (under reasonable hypotheses such as $|\log(b_n)|>\varepsilon$ for some fixed $\varepsilon>0$ and sufficiently large $n$). Note that

$$\frac{\log(a_n)}{\log(b_n)}=\frac{\log(b_n)+\log\left(\frac{a_n}{b_n}\right)}{\log(b_n)}.$$

This also implies that if $a_n\in\Theta(b_n)$ and $|\log(b_n)|\to\infty$, then $\log(a_n)\sim \log(b_n)$.

Solution 2:

Okay, lets work out the maths.

By the trapezoid rule, $\ln n! \approx \int_1^n \ln(x)\,{\rm d}x = n \ln n - n + 1$. Now we find the error in the approximation, which one can compute by Euler–Maclaurin formula. After some crude arithmetic, you can compute that

$$ \ln (n!) - \frac{\ln n}{2}= n \ln n - n + 1 + \sum_{k=2}^{m} \frac{\mathcal{B}_k\,(-1)^k}{k(k-1)} \left( \frac{1}{n^{k-1}} - 1 \right) + S_{m,n}, $$ where $\mathcal{B}_k$ denotes the Bernoulli's number.

Now taking limits, you can compute $$\lim_{n \to \infty} \left( \ln n! - n \ln n + n - \frac{\ln n}{2} \right) = 1 - \sum_{k=2}^{m} \frac{\mathcal{B}_k(-1)^k}{k(k-1)} + \lim_{n \to \infty} S_{m,n}$$.

Now since $S_{m,n}$ satisfies the following property, $$S_{m,n} = \lim_{n \to \infty} S_{m,n} + O \left( \frac{1}{n^m} \right),$$ we get the approximation in the logarithmic form. Taking exponent on both the sides and plugging $m=1$, we get the result: $$n! = \sqrt{2 \pi n}~{\left( \frac{n}{e} \right)}^n \left( 1 + O \left( \frac{1}{n} \right) \right).$$

If you don't care about the $\sqrt{2 \pi n}$ term, I guess you can just use the approximation $\ln n! \approx \sum_{j=1}^n \ln j$ as follows:

$$\sum_{j=1}^n \ln j \approx \int_1^n \ln x \,{\rm d}x = n\ln n - n + 1 = \Theta(n \ln n)$$.