2
$\begingroup$

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.

  • 0
    In that case, the proof will follow immediately as I have shown in the answer.2012-05-25

3 Answers 3

2

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

  • 0
    @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.2012-05-25
1

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

  • 0
    @Spyam - Ha symmetry.2012-05-25
1

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

  • 0
    Very sensible ;)2012-05-25