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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.