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

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

-
Are you aware of Stirlings formula and a proof for it? – user17762 May 25 '12 at 4:42
Yes, I certainly am. – Spyam May 25 '12 at 5:13
In that case, the proof will follow immediately as I have shown in the answer. – user17762 May 25 '12 at 5:16

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.$$

-
Andre: I have a suspicion this was the "expected" solution in the text, judging from comments elsewhere in the writing. Thank you very much for the help. – Spyam May 25 '12 at 5:18
@Spyam: The argument uses very little machinery. Versions of it come up a lot, when one is looking at the convergence of infinite series (Integral Test) and elsewhere. – André Nicolas May 25 '12 at 5:21

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

-
I think you've switched your $X$ and $n$ around by accident. Nice solution though! – Spyam May 25 '12 at 5:15
@Spyam - Ha symmetry. – Mark McClure May 25 '12 at 5:16

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).

-
Marvis, I'm extremely impressed how fast you managed to produce that! The last time I proved Stirling's formula was when I was 18 though which is a good couple years ago now; it's always nice to have a refresher, thank you. – Spyam May 25 '12 at 5:17
@Spyam I actually have lot of nice formulas, results and theorems and other other stuff typeset on my comp. Hence, it doesn't take a long time to copy paste it and make some minor modifications here and there :). – user17762 May 25 '12 at 5:18
Very sensible ;) – Spyam May 25 '12 at 5:20