mathschallenge.net logo

Harmonic Sum Approximation

Problem

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

  1. Prove that Hn approximately ln(n) + 1/(2n) + k, where 0.5 less than k less than 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 less than or equal x less than or equal 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 minus 1. And as this under-estimates the area:

Hn minus 1 less than ln(n)

therefore Hn less than ln(n) + 1

By using the Trapezium rule:


ln(n) approximately (1/2)[1 + 2(1/2 + 1/3 + ... + 1/(nminus1)) + 1/n]
  = 1 + 1/2 + 1/3 + ... + 1/n minus 1/(2n) minus 1/2
  = Hn minus 1/(2n) minus 1/2

But as the Trapezium rule is over-estimating the area in this case.

Hn minus 1/(2n) minus 1/2 greater than ln(n)

therefore Hn greater than ln(n) + 1/(2n) + 1/2.

Hence we establish upper and lower limits:

ln(n) + 1/(2n) + 1/2 less than Hn less than ln(n) + 1

therefore Hn approximately ln(n) + 1/(2n) + k, where 1/2 less than k less than 1 minus 1/(2n)

Although this by no means proves that k approximately 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):

nHnln(n) + 1/(2n)Error
110.50.5
21.50.9431471810.556852819
31.8333333331.2652789550.568054378
42.0833333331.5112943610.572038972
52.2833333331.7094379120.573895421
62.451.8750928030.574907197
72.5928571432.017338720.575518422
82.7178571432.1419415420.575915601
92.8289682542.2527801330.576188121
102.9289682542.3525850930.576383161
203.5977396573.0207322740.577007384
504.4992053383.9220230050.577182333
1005.1873775184.6101701860.577207332
10007.4854708616.9082552790.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 minus 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:

sum H
= H1 + H2 + ... + H100
  approximately 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)
  + 100times0.5772
  = ln(100!) + (1/2)H100 + 57.72
  approximately 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:

sum H
= H1 + H2 + ... + Hn
  = 1 + (1 + 1/2) + (1 + 1/2 + 1/3) + ... + (1 + 1/2 + ... + 1/n)
  = n + (nminus1)/2 + (nminus2)/3 + ... + 2/(nminus1) + 1/n
 
Writing n
= 1 + 2/2 + 3/3 + ... + (nminus1)/(nminus1) + n/n
 
sum 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 sum H = (n+1)Hn minus 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) minus 100 approximately 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