
Harmonic Sum Approximation
Problem
Hn = 1 + 1/2 + 1/3 + ... + 1/n is defined as the nth Harmonic number.
- Prove that Hn
ln(n) + 1/(2n) + k, where 0.5
k
1.
- By using k = 0.5772, estimate the sum of the first one hundred Harmonic numbers.
Solution
Consider the graph y = 1/x for 0 x
5:
The exact area below the curve from 1 to n is given by | ![]() |
| 1/x dx = ln(n) |
By using rectangles, it can be seen that the approximate area is given by,
1/2 + 1/3 + 1/n = Hn 1. And as this under-estimates the area:
Hn 1
ln(n)
Hn
ln(n) + 1
By using the Trapezium rule:
ln(n) | ![]() | (1/2)[1 + 2(1/2 + 1/3 + ... + 1/(n![]() |
= | 1 + 1/2 + 1/3 + ... + 1/n ![]() ![]() | |
= | Hn ![]() ![]() |
But as the Trapezium rule is over-estimating the area in this case.
Hn 1/(2n)
1/2
ln(n)
Hn
ln(n) + 1/(2n) + 1/2.
Hence we establish upper and lower limits:
ln(n) + 1/(2n) + 1/2 Hn
ln(n) + 1
Hn
ln(n) + 1/(2n) + k, where 1/2
k
1
1/(2n)
Although this by no means proves that k 0.5772, using a spreadsheet, and working to 10 d.p., let us consider the error between Hn and the approximation ln(n) + 1/(2n):
n | Hn | ln(n) + 1/(2n) | Error |
1 | 1 | 0.5 | 0.5 |
2 | 1.5 | 0.943147181 | 0.556852819 |
3 | 1.833333333 | 1.265278955 | 0.568054378 |
4 | 2.083333333 | 1.511294361 | 0.572038972 |
5 | 2.283333333 | 1.709437912 | 0.573895421 |
6 | 2.45 | 1.875092803 | 0.574907197 |
7 | 2.592857143 | 2.01733872 | 0.575518422 |
8 | 2.717857143 | 2.141941542 | 0.575915601 |
9 | 2.828968254 | 2.252780133 | 0.576188121 |
10 | 2.928968254 | 2.352585093 | 0.576383161 |
20 | 3.597739657 | 3.020732274 | 0.577007384 |
50 | 4.499205338 | 3.922023005 | 0.577182333 |
100 | 5.187377518 | 4.610170186 | 0.577207332 |
1000 | 7.485470861 | 6.908255279 | 0.577215582 |
In fact, k = 0.5772156649 (10 d.p.) is called the Euler-Mascheroni constant and appears in many other contexts; for example, the average number of divisors of all the numbers from 1 to n is approximately ln(n) + 2k 1. Although k is suspected to be transcendental, no one so far has even established if it is irrational. Care to prove it?
At this stage it may be tempting to use this approximation to sum the first one hundred Harmonic numbers:
![]() | = | H1 + H2 + ... + H100 |
![]() | ln(1)+1/2+0.5772 + ln(2)+1/4+0.5772 + ... | |
+ ln(100)+1/200+0.5772 | ||
= | ln(1)+ln(2)+...+ln(100) + (1/2)(1+1/2+...+1/100) | |
+ 100![]() | ||
= | ln(100!) + (1/2)H100 + 57.72 | |
![]() | ln(100!) + (1/2)(ln(100)+1/200+0.5772) + 57.72 | |
= | ln(100!) + ln(10) + 58.0411 |
However, not many calculators can evaluate 100!, and we would expect the error accumulated in one hundred and one approximations to be significant. It turns out that this compound approximation gives an answer of 424.083 (3 d.p.), which, as we shall see, is only correct to the nearest whole number.
Instead we shall consider the general sum of the first n Harmonic numbers:
![]() | = | H1 + H2 + ... + Hn |
= | 1 + (1 + 1/2) + (1 + 1/2 + 1/3) + ... + (1 + 1/2 + ... + 1/n) | |
= | n + (n![]() ![]() ![]() | |
Writing n | = | 1 + 2/2 + 3/3 + ... + (n![]() ![]() |
![]() | = | (n+1) + (n+1)/2 + (n+1)/3 + ... + (n+1)/n |
= | (n+1)(1 + 1/2 + 1/3 + ... + 1/n) | |
= | (n+1)Hn |
Therefore H = (n+1)Hn
n.
This is a much better approach as we need only make one approximation to find the sum: 101(ln(100) + 1/200 + 0.5772) 100
423.924; incredibly the actual sum, without using the approximation, is 423.925 (3 d.p.).