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 , which can be defined as .
Most students know that it is about , but they don’t know the proof.
The proof is, however, quite simple.
For simplicity, assume that is a power of two, i.e., for some positive integer a.
We group terms in the sum like this:
Note that each group in the sum is at most 1 and at least 1/2. And we have groups.
Thus, this shows that when for some positive integer a. Now, to get to general k should be an easy exercise.
A more accurate estimate for is where is the Euler-Mascheroni constant (see wikipedia article).