Showing that Harmonic numbers are $\Theta(\log n)$, intuitively

Question

I wish to verify that Harmonic numbers $H_n = \sum_{k=1}^{n} \frac{1}{k}$ are $\Theta(\log n)$.

One idea I have is to approximate the sum with an integral:

$$\int_{1}^{n} \frac{1}{k} ~dk = \log(n) - \log(1) = \log(n)$$

But I don't know if this is valid and I want a more direct proof.

In other words I want to show that:

$$\sum_{k=1}^{n} \frac{1}{k} \leq c \log n$$

and

$$\sum_{k=1}^{n} \frac{1}{k} \geq d \log n$$

For some $n \geq n_0$ and positive reals $c,d$. Is there an intuitive way to do this that doesn't rely on weird calculus tricks? I see derivations in the post here:

Simple proof of showing the Harmonic number $H_n = \Theta (\log n)$

but none of these seem intuitive to me (they rely on higher calculus and series tests and Riemann sums).

Answer 1

\begin{align} & \frac 1 2 \le \int_1^2 \frac{dx} x \le 1 \\[8pt] & \frac 1 3 \le \int_2^3 \frac{dx} x \le \frac 1 2 \\[8pt] & \frac 1 4 \le \int_3^4 \frac{dx} x \le \frac 1 3 \\[8pt] & \qquad \qquad \vdots \\[10pt] \text{Hence } & \frac 1 2 + \frac 1 3 + \frac 1 4 + \cdots + \frac 1 {n+1} \le \int_1^{n+1} \frac{dx} x \le 1 + \frac 1 2 + \frac 1 3 + \cdots + \frac 1 n. \end{align} And finally, $$ 1 + \int_1^n \frac{dx} x \ge 1+ \frac 1 2 + \frac 1 3 + \cdots + \frac 1 n \ge \int_1^{n+1} \frac {dx} x, $$ i.e. $$ 1 + \log n \ge H_n \ge \log(n+1). $$

Answer 2

Your idea of approximation with an integral works. This is a classical exercise: let $f\colon x > 0\mapsto \frac{1}{x}$ (works with any monotone function $f$ such that $\lim_{x\to \infty}f(x) = 0$):

Fix any $n \geq 1$. For all $n \leq x \leq n+1$, $$ f(n+1) \leq f(x) \leq f(n) $$ so that, integrating, $$ f(n+1) = \int_n^{n+1} f(n+1) dx \leq\int_n^{n+1} f(x) dx \leq \int_n^{n+1} f(n) dx = f(n) $$ which holds for any integer $n\geq 1$. Now, sum this inequality for $n$ ranging from $1$ to $N-1$: $$ \sum_{n=1}^{N-1} f(n+1) \leq \sum_{n=1}^{N-1} \int_n^{n+1} f(x) dx \leq \sum_{n=1}^{N-1} f(n) $$ that is exactly (using for the middle term that $\int_a^b f + \int_b^c f = \int_a^c f$): $$ \sum_{n=2}^{N} f(n) \leq \int_1^{N} f(x) dx \leq \sum_{n=1}^{N-1} f(n). $$ Rearranging, $$ \int_1^{N} f(x) dx + f(N) \leq \sum_{n=1}^{N} f(n) \leq f(2) + \int_1^{N} f(x) dx $$ which gives, in our case, $$ \ln N + \frac{1}{N} \leq \sum_{n=1}^{N} f(n) \leq \frac{1}{2} + \ln N $$

Answer 3

Here's a direct approach that avoids calculus to obtain just the weak result of $\Theta(\log n)$ rather than the more precise asymptotic $(1+o(1)) \log n$.

First consider the special case that $n$ is of the form $2^k - 1$, and divide $H_n$ into dyadic blocks:

$$H_n = \big(1\big) + \big(\frac12 + \frac13\big) + \big(\frac14 + \cdots + \frac17\big) + \cdots + \big(\frac{1}{2^{k-1}} + \cdots + \frac1{2^k-1}\big),$$ where there are $k$ blocks and each block has twice the number of terms as the previous one. Now the following two inequalities are obvious by term-by-term comparison:

$$H_n \le \big(1\big) + \big(\frac12 + \frac12\big) + \big(\frac14 + \cdots + \frac14\big) + \cdots + \big(\frac{1}{2^{k-1}} + \cdots + \frac1{2^{k-1}}\big) = 1 + 1 + \cdots + 1 = k,$$

$$H_n \ge \big(\frac12\big) + \big(\frac14 + \frac14\big) + \big(\frac18 + \cdots + \frac18\big) + \cdots + \big(\frac{1}{2^k} + \cdots + \frac1{2^k}\big) = \frac12 + \frac12 + \cdots + \frac12 = \frac k2.$$

Therefore, for these special values of $n$, $\frac k2 \le H_n \le k$. Since $k = \log(n+1)/\log 2$, this is clearly $\Theta(\log n)$. This gives the intuition (which your question explicitly asks for), now to fill in the details for arbitrary $n$ you just need to use the fact that $H_n$ is monotonically increasing and that you can always find consecutive powers of $2$ that bracket $n$.

Answer 4

You can show that as $n \to \infty$ we have the asymptotic behavior

$$H_n \sim \log n,$$

directly as a limit of a sequence.

By the Stolz-Cesaro theorem (L'Hospital's rule for sequences)

$$\lim_{n \to \infty} \frac{H_n}{\log n} = \lim_{n \to \infty} \frac{H_{n+1}- H_n}{\log (n+1) - \log n} \\ = \lim_{n \to \infty}\frac{1/(n+1)}{\log(1 + 1/n)} \\ = \lim_{n \to \infty}\frac{1}{\log(1 + 1/n)^{n+1}} \\ = \frac{1}{\log e} \\ = 1.$$