# Hk

Yesterday I taught a bunch of smart high-school students at the national preparation camp for IOI.

I covered a bunch of topics, including a very nice proof of Sperner’s lemma.

At some point, we were talking about the k-th harmonic numer $H_k$, which can be defined as $H_k = \frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{k}$.

Most students know that it is about $O(\log k)$, but they don’t know the proof.

The proof is, however, quite simple.

For simplicity, assume that $k+1$ is a power of two, i.e., $k = 2^a - 1$ for some positive integer a.

We group terms in the sum like this:

$\left(\frac{1}{1}\right) + \left(\frac{1}{2} + \frac{1}{3}\right) + \left(\frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7}\right) + \cdots + \left(\frac{1}{2^{a-1}}+\cdots+ \frac{1}{2^a - 1}\right)$.

Note that each group in the sum is at most 1 and at least 1/2. And we have $\log(k+1)$ groups.

Thus, this shows that $\frac{1}{2}\cdot\log(k+1)\leq H_k\leq\log(k+1)$ when $k=2^a - 1$ for some positive integer a. Now, to get to general k should be an easy exercise.

A more accurate estimate for $H_k$ is $\ln k + \gamma$ where $\gamma$ is the Euler-Mascheroni constant (see wikipedia article).