 ## Harmonic Sum Approximation

#### Problem

Hn = 1 + 1/2 + 1/3 + ... + 1/n is defined as the nth Harmonic number.

1. Prove that Hn ln(n) + 1/(2n) + k, where 0.5 k 1.
2. 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 n 1
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/n] = 1 + 1/2 + 1/3 + ... + 1/n 1/(2n) 1/2 = Hn 1/(2n) 1/2

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: H = 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 0.5772 = 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: H = H1 + H2 + ... + Hn = 1 + (1 + 1/2) + (1 + 1/2 + 1/3) + ... + (1 + 1/2 + ... + 1/n) = n + (n 1)/2 + (n 2)/3 + ... + 2/(n 1) + 1/n Writing n = 1 + 2/2 + 3/3 + ... + (n 1)/(n 1) + n/n H + 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.).

Problem ID: 209 (17 Feb 2005)     Difficulty: 4 Star

Only Show Problem