Big-$\mathcal{O}$ bounding of sums of logarithmic functions

Question

I am reading a text which states that $$\sum \limits_{n \leq X} \left(\log X - \log n \right) = \mathcal{O}(X)$$ I can't quite see why this is true, though I can certainly believe it. Could anyone explain how to show this?

We can rewrite this as $\displaystyle \sum_{n \leq X} \log(X/n)$, and I guess the idea behind this would be to use the fact that for "most" terms in the sum, $n \approx x$ so $\log(X/n) \approx 0$, and there are only a "few" small values of $n$ for which $\log(X/n) \approx \log(X)$. Formally proving it however, has eluded me.

To reiterate, I would like to see a proof that $$\sum_{n \leq X} \left(\log X - \log n \right) = O(X)$$

Many thanks for your help.

Answer 1

Hint: For simplicity let $X$ be an integer. By approximating $\log t$ by a step function, show that $$\log 1+\log 2+\cdots +\log X \ge \int_2^X \log t\,dt.$$ Then use the fact that $$\int \log t \,dt=t\log t-t.$$

Answer 2

Well, $$\sum_{n\leq X} (\log(X) - \log(n)) = \log(X!) - n\log(n).$$ Now, apply Stirling's formula to $\log(X!)$.

Answer 3

The main thing you need is a weak version of Stirling's formula. We state the Stirling's formula here. $$\displaystyle N! \sim \sqrt{2 \pi N} \left( \frac{N}{e}\right)^N.$$

This gives us $\log(N!) \sim N \log N - N + \dfrac12 \log N + \dfrac12 \log(2 \pi)$. Hence, $$\sum_{n \leq X} \left( \log X - \log n \right) = X \log(X) - \log(X!) = X - \dfrac12 \log(X) - \dfrac12 \log(2 \pi) + \mathcal{O}(1/X)$$

Below is a proof for the Stirling's formula (except for the constant $\sqrt{2 \pi}$).

Claim:

$\displaystyle N! \sim K \sqrt{N} \left( \frac{N}{e}\right)^N$.

Note that $\displaystyle \log(N!) = \sum_{n \leq N} \log(n)$. Choose $a(n) = 1$, $f(n) = \log(n)$ and let $A(t) = \displaystyle \sum_{n \leq t} a(n)$. Hence, we have that $$\displaystyle \log(N!) = \sum_{n \leq N} \log(n) = \int_{1^-}^{N^+} \log(t) dA(t)$$ where $\displaystyle A(t) = t - \{t \}$ and the integral is the Riemann-Stieltjes integral. Hence, we get that $$\displaystyle \log(N!) = \left. (t-\{t\}) \log(t) \right \rvert_{1^-}^{N^+} - \int_{1^-}^{N^+} \frac{(t-\{t\})}{t}dt = N \log (N) - (N-1) + \int_{1^-}^{N^+} \frac{\{t\}}{t} dt.$$ $$\int_{1^-}^{N^+} \frac{\{t\}}{t} dt = \int_{1^-}^{N^+} \frac{\{t\}-1/2}{t} dt + \int_{1^-}^{N^+} \frac{1}{2t} dt = \frac{\log (N)}2 + \int_{1^-}^{N^+} \frac{B(t)}{t} dt$$ where $B(t) = \{t\} - \frac12$. $$\int_{1^-}^{N^+} \frac{B(t)}{t} dt = \int_{1^-}^{N^+} \frac{dB_1(t)}{t} = \left. \frac{B_1(t)}{t} \right|_{1^-}^{N+} + \int_{1^-}^{N^+} \frac{B_1(t)}{t^2} dt = \int_{1^-}^{N^+} \frac{B_1(t)}{t^2} dt$$ where $B_1(t) = \frac{\{t\}^2 - \{t\}}{2}$. $$\int_{1^-}^{N^+} \frac{B_1(t)}{t^2} dt = \int_{1^-}^{\infty} \frac{B_1(t)}{t^2} dt - \int_{N^+}^{\infty} \dfrac{B_1(t)}{t^2} dt$$ Hence, $$\log (N!) = N \log(N) - N + 1 + \frac{\log(N)}{2} + \int_{1^-}^{\infty} \frac{B_1(t)}{t^2} dt - \int_{N^+}^{\infty} \frac{B_1(t)}{t^2} dt.$$ $$\int_{1^-}^{\infty} \frac{B_1(t)}{t^2} dt = -\frac1{12} + \int_{1^-}^{\infty} \frac{d B_2(t)}{t^2} = -\frac1{12} + 2 \int_{1^-}^{\infty} \frac{B_2(t)}{t^3} dt$$ where $B_2(t) = \displaystyle \int_0^{\{t\}} \left( B_1(y) + \frac12 \right) dy$ $$\int_{1^-}^{N^+} \frac{B_1(t)}{t^2} dt = -\int_{1^-}^{N^+} \frac{1}{12t^2} dt + \int_{1^-}^{N^+} \frac{dB_2(t)}{t^2} = -\frac1{12N} + \left. \frac{B_2(t)}{t^2} \right|_{1^-}^{N+} + 2 \int_{1^-}^{N^+} \frac{B_2(t)}{t^3} dt$$ Note that $B_1(t) = \mathcal{O}(1)$. Hence, $\displaystyle \int_{N^+}^{\infty} \frac{B_1(t)}{t^2} dt = \mathcal{O}(1/N)$. Hence, we get that $$\log (N!) = N \log(N) - N + \frac{\log(N)}{2} + C + \mathcal{O}(1/N).$$ Hence, we get that $$\log (N!) \sim N \log(N) - N + \frac{\log(N)}{2} + C = \log(N^N \exp(c-N) \sqrt{N}).$$ Hence, $$N! \sim K \sqrt{N} \left( \frac{N}{e} \right)^N.$$ The constant $K = \sqrt{2 \pi}$ is typically tricky to obtain. It is a good exercise to prove that $K = \sqrt{2 \pi}$.

The $B_k(y)$ are related to the Bernoulli's polynomial (almost the same as Bernoulli polynomial except for the constant term probably).