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

asymptoticsharmonic-numbersnumber theoryproof-verification

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

Best Answer

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

Related Question