# Calculus-Free Asymptotic for Harmonic Numbers

Here we prove that $H_n = \Theta(\log_2 n)$ without touching calculus (the most common proof interprets $H_n$ as a Riemann sum of $\int 1/x$). Seeing as this is probably the most fundamental asymptotic for computer scientists, I was surprised to see this Stack Exchange question didn’t mention the calculus-free approach. The proof here pretty much matches my own answer to the Stack Exchange post.

We first consider powers of 2, $n = 2^k$. For these $n$, we can break up $\sum \frac{1}{j}$ into the “chunks”

$1$

$\frac{1}{2} + \frac{1}{3}$

$\frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7}$

$\dots$

$\frac{1}{2^{k-1}} + \cdots + \frac{1}{2^k - 1}$

and we have one extra term $1/2^k$. There are $k + 1 = \log_2 n + 1$ chunks, and of course $H_n$ is the sum of these chunks (plus the extra term), hence to show $H_n = \Theta(\log_2 n)$ we show each chunk is $\Theta(1)$. Inside each chunk we bound above by the power of 2:

$1 \leq 1$

$\frac{1}{2} + \frac{1}{3} \leq \frac{1}{2} + \frac{1}{2} = 1$

$\frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} \leq \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} =1$

$\dots$

$\frac{1}{2^{k-1}} + \cdots + \frac{1}{2^k - 1} \leq \frac{1}{2^{k-1}} + \cdots + \frac{1}{2^{k - 1}} = 1$

Thus each chunk is at most 1, and taken together with the extra term $\frac{1}{2^k}$, we have $H_n \leq \log_2 n + \frac{1}{2^k} \leq \log_2 n + 1$.

On the other hand, if we lower bound the elements by the next power of 2,

$1 \geq 1$

$\frac{1}{2} + \frac{1}{3} \geq \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$

$\frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} \geq \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} =\frac{1}{2}$

$\dots$

$\frac{1}{2^{k-1}} + \cdots + \frac{1}{2^k - 1} \geq \frac{1}{2^k} + \cdots + \frac{1}{2^k} = \frac{1}{2}$

Every chunk is at least $\frac{1}{2}$, hence $H_n \geq \frac{1}{2}\log_2 n$.

This essentially is the proof. One technicality: we’ve only shown $H_n = \Theta (\log_2 n)$ for $n$ a power of 2. Monotonicity of $H_n$ completes the proof for all $n$: taking the nearest powers of 2 above and below $n$, call them $n_-$ and $n_+$,

$n/2 < n_- < n < n_+ < 2n$

Applying our bounds on $H_{n_-}$ and $H_{n_+}$,

$H_n \leq H_{n_+} \leq \log_2 n_+ + 1 < \log_2 (2n) +1= \log_2 n + 2$

$H_n \geq H_{n_-} \geq \frac{1}{2}\log_2 n_- > \frac{1}{2}\log_2 (n/2) = \frac{1}{2}\log_2 n - \frac{1}{2}$

Thus $H_n = \Theta(\log_2 n)$.

(In general, for any monotonic linear or sublinear function, it suffices to show $\Theta(\cdot)$ on only the powers of 2).