How do I show, when $n$ is large, that the Harmonic number is approx $\log n$?

Question

I want to show $H_n \approx \log n $ when $n$ is large.

It is part of a bigger problem where I must prove $$\sum_{i=1}^{n-1} \frac{n-1}{n-i} \approx n\log n.$$

$(H_n=\sum_{j=1}^{n} \frac{1}{j})$ Any help is appreciated, thank you.

Answer 1

Obviously, as the inverse is a monotonous function,

$$\int_1^n\frac{dx}{\lceil x\rceil}\le\int_1^n\frac{dx}x\le\int_1^n\frac{dx}{\lfloor x\rfloor}.$$

Then

$$\sum_{k=2}^n\frac1k\le\left.\log x\right|_1^n\le\sum_{k=1}^{n-1}\frac1k,$$ and

$$H_n-1\le\log n\le H_n-\frac1n.$$

Finally

$$\log n+\frac1n\le H_n\le\log n+1.$$

---

The bracketing is not very tight. We can improve it by taking some $k$ instead of $1$ for the lower bound.

This gives $$H_n-H_k\le\log n-\log k\le H_n-H_{k-1}-\frac1n$$

or

$$\log n+\frac1n-\frac1k+H_k-\log k\le H_n\le\log n+H_k-\log k.$$

Answer 2

A good estimate comes from approximating your sum by the integral $$ \int_1^{n-1} \frac{n-1}{n - x} dx = -(n-1) \ln(n-x)\Bigg|_1^{n-1} = (n-1)\ln(n-1) \approx n \ln n.$$ This estimate can be made more formal and precise by following an argument similar to the standard proofs of the integral test for convergence of an infinite series.

This works directly for showing that $H_n \approx \log n$ as well. In particular, $$ \int_1^{n} \frac{1}{x} dx \leq H_n \leq 1 + \int_1^{n} \frac{1}{x} dx$$ and so $$ \ln n \leq H_n \leq 1 + \ln n.$$

---

Note, it is possible to produce better estimates.

A better estimate comes from thinking of your sum as a Riemann-Stieltjes integral $$ \sum_{i = 1}^{n-1} \frac{n-1}{n-i} = \int_1^{n-1} \frac{n-1}{n-x} d \lfloor x \rfloor$$ and then integrating by parts, or by performing Abel's summation, or by performing summation by parts (all of which are essentially the same thing). But