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