Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer
    
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!)$.

share|improve this answer
    
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).

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.