The Celebrated Harmonic Numbers and How to Approximate Them
We discuss the famous harmonic sum and describe a simple way to approximate it.
It is very likely that, if you regularly read textbooks or research papers on Mathematics, Computer Science or related fields, at some point you stumbled upon what is known as the harmonic sum, which is simply the following sum:
The number H(n) is called the n-th Harmonic Number.
Besides appearing in many different applications (see, e.g., one of my previous articles on the Coupon Collector problem, where a calculation about an expected value ends up being the harmonic sum), it is a very natural sum to consider, and the intellectual curiosity of any mathematician would oblige them to study it!
The main task of today’s article is to get a good estimate on H(n).
Computations
We start with a simple observation. Each term of the sum can be interpreted as the area of a rectangle with width equal to 1 and height equal to 1/i. Thus, H(n)can be described as a sum of the areas of certain rectangles. This is depicted as the yellow area in the following figure.
Note that the rectangles are placed in such a way, so that the graph of the function f(x) = 1/x for x ≥ 1 passes through the top left corner of each rectangle, and is contained in the yellow area.
It is indeed easy to verify that H(n) is now equal to the sum of the areas of the first n rectangles of the figure. From the above figure, we immediately get that the yellow area is at least as large as the area contained below the red line, or in other words, the yellow area is at least as large as the area contained between the graph of the function f(x) = 1/x and the x-axis. Thus, we get the following:
This is already a good lower bound, which, in particular, shows that as n grows, H(n) becomes unbounded, or in other words, the harmonic series diverges:
Still, we would like to be a bit more precise. By using the figure, it is not hard to observe that if we ignore the first term of the harmonic sum and shift the rectangles one unit to the left, then the function f(x) = 1/x covers at least as much area as the remaining rectangles. Pictorially, this is shown in the figure below.
The above figure now implies that:
We conclude that
In particular, we get that
The above bounds imply that for any n, if we simply compute ln n instead of H(n), then our error will be at most 1!
Refining the approximation
With significantly more work (that is out of scope of this article), one can show that the error term in the above approximation converges to a constant that is, in fact, even smaller than 1, and is none other than the famous Euler–Mascheroni constant, which is formally defined as:
The first 50 decimal digits of this constant are:
γ = 0.57721566490153286060651209008240243104215933593992.
Using this constant, one can show that the n-th Harmonic Number, for all practical purposes, is equal to the following:
Conclusion
In this article, we discussed the famous harmonic sum and the corresponding sequence of numbers H(n) that we get, and we showed that they, more or less, behave like the sequence {ln n}, n = 1, ….
There are many sources available online discussing the approximation of the harmonic sum, and the interested reader is particularly encouraged to read more about the Euler-Mascheroni constant, which, to this day, is not known whether it is an algebraic or transcendental number, and, in fact, it is not even known whether it is irrational!
