mathschallenge.net

Problem

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

1. Prove that H_n 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 = H_n 1. And as this under-estimates the area:

H_n 1 ln(n)

H_n ln(n) + 1

By using the Trapezium rule:

ln(n)		(1/2)[1 + 2(1/2 + 1/3 + ... + 1/(n1)) + 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.

H_n 1/(2n) 1/2 ln(n)

H_n ln(n) + 1/(2n) + 1/2.

Hence we establish upper and lower limits:

ln(n) + 1/(2n) + 1/2 H_n ln(n) + 1

H_n 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 H_n and the approximation ln(n) + 1/(2n):

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)
		+ 1000.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 + (n1)/2 + (n2)/3 + ... + 2/(n1) + 1/n
Writing n	=	1 + 2/2 + 3/3 + ... + (n1)/(n1) + 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)H_n 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.).