# Prove that $\sum_{k=1} ^ n k^{-1} = \ln(n) + O(1)$

I would like to prove that $\sum_{k=1} ^ n k^{-1} = \ln(n) + O(1)$. That is, I would like to show that there is some natural number $N$ large enough so that $n \ge N$ implies:

$$|\sum_{k=1}^n k^{-1} - \ln(n) | < M,$$

where $M$ is a positive constant independent of $n$. I think the idea behind the argument must be easy, but I am somehow missing it. I do see that $\sum_{k=1}^n k^{-1}$ can be taken as a sort of approximation, using areas of rectangles, to $\int_1^n \frac{1}{x}dx = \ln(n)$. So maybe the argument uses the integral comparison test? But, anyway, I'm still fumbling with how to proceed.

Hints or solutions are greatly appreciated.

• There is a neat proof that $H_n-\log n\to\gamma$ using monotone convergence (monotone bounded sequence converges), would you like that? – Pedro Tamaroff Mar 10 '13 at 23:58
• You might want to look at the Wikipedia article on Euler's constant. – Aeolian Mar 11 '13 at 0:00
• @PeterTamaroff I'm just realizing by looking at the Wikipedia on this subject--this may be heavier analysis than I'm comfortable working with. I do know the monotone convergence, though, so I'd really like to see that proof. – JZS Mar 11 '13 at 0:05
• @jtms88 I'm writing it. – Pedro Tamaroff Mar 11 '13 at 0:26

It is clear that $k^{-1}$ is decreasing. For any decreasing function $f(x)$, we have that:

$$\int_{a}^{b+1} f(i) \; \mathrm d i \le \sum_{i=a}^b f(i) \le \int_{a-1}^b f(i) \; \mathrm d i$$

Upper Bound

Evaluate the first term of the sum to get that (you may find it instructive to see what happens if we don't evaluate the first term and try to approximate as is):

$$1 + \sum_{k=2}^n \frac{1}{k} = \sum_{k=1}^n \frac{1}{k}$$

Now:

$$1 + \sum_{k=2}^n \frac{1}{k} \le 1 + \int_{1}^n \frac{1}{i} \; \mathrm di$$ $$\sum_{k=1}^n \frac{1}{k} \le 1 + \ln n$$

(for $n>1$)

Lower Bound

By the same method, except with the lower bound used:

$$\frac{1}{n} + \int_{1}^{n} f(i) \; \mathrm d i \le \frac{1}{n} + \sum_{k=1}^{n-1} \frac{1}{k}$$ $$\frac{1}{n} + \ln(n) \le \sum_{k=1}^n \frac{1}{k}$$

(Implying that the sum is bounded)

So we have:

$$\left| \sum_{k=1}^n \frac{1}{k} - \ln n\right| < M$$ $$\left| 1 + \ln n - \ln n \right| < M$$ $$1 < M$$

• You actually still need to prove a analogous lower bound for $\sum_{k=1}^{n}{\frac{1}{n}}$. – Ivan Loh Mar 11 '13 at 0:12
• @IvanLoh, perhaps I am missing something, can you explain why I need to prove the lower bound as well? – George V. Williams Mar 11 '13 at 0:17
• If you only have an upper bound, note the counter-example $1 \leq 1+\ln n$, but $|1-\ln n|$ is not bounded. – Ivan Loh Mar 11 '13 at 0:26
• @IvanLoh, I added the lower bound. Is it correct now? Thanks for your input. – George V. Williams Mar 11 '13 at 0:31
• Yes it is alright now. – Ivan Loh Mar 11 '13 at 0:50

For each $k\geq 1$, define $$g_k=\frac 1 k-\int_{k}^{k+1}\frac{dx}x$$

Observe that since $x^{-1}$ is decreasing, $g_k>0$ for each $k$. Moreover, for each $k$ $$g_k<\frac 1k -\frac 1{k+1}$$

Thus, for each $n$

$$0<\sum_{k=1}^n g_k< 1-\frac 1{n+1}$$

Since each $g_k$ is positive, $$G_n=\sum_{k=1}^n g_k$$ is monotone increasing, moreover $$\lim\left( 1-\frac 1{n+1}\right)=1$$ which means $G_n$ is bounded above by $1$. By the monotone convergence theorem, $\lim G_n$ exists. But

$$G_n=\sum\limits_{k = 1}^n {{g_k}} = {H_n} - \log \left( {n + 1} \right)$$

Thus ${H_n} - \log \left( {n + 1} \right)\to \gamma$ a constant, $0<\gamma <1$.

NOTE Observe that the above means, since $$\log \left( {1 + {1 \over n}} \right)\to 0$$ that $${H_n} - \log n \to \gamma$$ as well.

• How do you justify the step that $g_k < \frac{1}{k} - \frac{1}{k+1}$? – George V. Williams Mar 11 '13 at 0:41
• $x^{-1}$ is monotone decreasing, which means $$\int_k^{k+1}\frac{dx}x<\frac{1}{k}$$ Multiply by $-1$ and add $\frac 1{k+1}$ – Pedro Tamaroff Mar 11 '13 at 0:50
• I see it now, thanks (upvoted). – George V. Williams Mar 11 '13 at 0:55

Start with the expansion valid for $0 < x < 1$ $$-\ln(1-x) = \sum_{k=1}^{\infty} \frac{x^k}{k}$$

Then

\begin{align} \ln(n) - \ln(n-1) &= \ln(\frac{n}{n-1}) \\ &= -\ln(\frac{n-1}{n}) \\ &=-\ln(1-\frac1{n}) \\ &=\sum_{k=1}^{\infty} \frac1{k n^k} \\ &= \frac1{n} +\sum_{k=2}^{\infty} \frac1{k n^k} \\ \end{align}

so $\ln(n) - \ln(n-1) > \frac1{n}$.

For an upper bound,

\begin{align} \sum_{k=2}^{\infty} \frac1{k n^k} &=\frac1{n^2}\sum_{k=2}^{\infty} \frac1{k n^{k-2}} \\ &<\frac1{n^2}(\sum_{k=0}^{\infty} \frac1{n^k})\\ &=\frac1{n^2}\frac1{1-1/n}\\ &=\frac1{n(n-1)}\\ &=\frac1{n-1}-\frac1{n}\\ \end{align}

so $\ln(n) - \ln(n-1) -\frac1{n} < \frac1{n-1}-\frac1{n}$.

Summing from $n=2$ to $N$,

$$0 < \sum_{n=2}^N \left(\ln(n) - \ln(n-1) -\frac1{n}\right) < \sum_{n=2}^N \left(\frac1{n-1}-\frac1{n}\right)$$

or $$0 < \ln(N) - \sum_{n=2}^N \frac1{n} < 1-\frac1{N}$$

Note: This, of course, is not in any way original, but I enjoyed reconstructing it on the fly, doing the math in my head as I went along.

• Nice one. It is interesting you arrived to bounds very similar to my bounds (well... Landau's). – Pedro Tamaroff Mar 11 '13 at 1:31
• Starting with the series for -ln(1-x), the conclusion seems almost inevitable. It seems like the start of the derivation of the simplest form of the Euler-McLaurin sum formula, using ln(x) and 1/x for $\int f$ and $f$. – marty cohen Mar 11 '13 at 1:38