In perfect harmony

September 2000

Introduction

Two elementary series are studied in school mathematics:

arithmetic series, such as $1+2+3+\dots +n$

and

geometric series, such as $1+2+2^2+\dots +2^{n-1}.$

There is an equally elementary series, called the harmonic series:

$1 + 1/2 + 1/3 + \dots +1/n.$

Though elementary in form, the harmonic series contains a good deal of fascinating mathematics, some challenging Olympiad problems, several surprising applications, and even a famous unsolved problem. There are a number of questions about the harmonic series which have answers that initially offend our intuition, and therefore have particular relevance to mathematics teaching and learning.

Why is the series called "harmonic"?

Fifths

The name originated with the Greeks, who as we know had words for many things. It was Pythagoras who was the first person to study the notes emitted by plucked strings of various lengths. If a string which emits middle C when plucked is reduced to two-thirds of its length, it will emit the note G (musicians call the interval from C to G a fifth). If the string is halved in length, it will emit top C, an octave higher. These notes are fundamental to the Pythagorean theory of harmony, and the corresponding lengths of string

1 2/3 1/2

are said to be in harmonic progression, with 2/3 the harmonic mean of 1 and 1/2. Now the inverses of these numbers

1 3/2 2

form an arithmetic progression, and so it is that a sequence of numbers whose inverses are in arithmetic progression is said to be in harmonic progression.

The Cube and the Octahedron

Pythagoras mixed his mathematics and physics with a liberal helping of mystical mumbo-jumbo. He noted, for example, that a cube has 6 faces, 8 vertices, and 12 edges. Since 6, 8 and 12 are in harmonic progression, to Pythagoras the cube was a "harmonic" body. Are there any other "harmonic" bodies? There is the octahedron, with 8 faces, 12 edges and 6 vertices. Are there any others? It's a simple enough question, but I've not seen it asked before. The problem of finding all harmonic bodies requires a knowledge of Euler's formula for polyhedra and Pell's equation for its solution.

The sum of harmonic series

There is no simple formula, akin to the formulae for the sums of arithmetic and geometric series, for the sum

$1 + 1/2 + 1/3 + \dots +1/n.$

Nevertheless, we can answer the question: What is the sum "to infinity" of the harmonic series?

You might be excused for thinking that the sum to infinity of the harmonic series is some finite number, because as you add more and more terms, less and less is added to the running total. Indeed, if you asked your friendly pocket calculator or home computer to sum the series, you would get a finite sum. That is because your typical calculator handles numbers only up to a certain size (usually 10¹⁰⁰), and would regard 1/(10¹⁰⁰+1) as zero. Such a calculator would tell you that the sum of the harmonic series is about 230, if you let it run long enough.

However, the harmonic series actually diverges - the sum increases without bound. This surprising result was first proved by a mediaeval French mathematician, Nichole Oresme, who lived over 600 years ago. He noted that if you replace the series

$1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 + 1/11 +\dots$

by the series of lesser terms

$1 + 1/2 + \left(1/4 + 1/4\right) + \left(1/8 + 1/8 + 1/8 + 1/8\right) + \left(1/16 + 1/16 + \dots + 1/16 \right) +\dots$

and bracket the terms as shown, then the latter series is just

$1 + 1/2 + 1/2 + 1/2 + 1/2 + \dots$

whose sum can clearly be made as large as we please.

If $H(n)$ is used to denote the sum to $n$ terms of the harmonic series, then Oresme's argument shows that

$H(2^ n) \geq \frac{n+2}{2}.$

So $H(n)$ creeps ever more slowly to infinity, increasing by smaller and smaller steps. It is an interesting observation that, after $H(1)=1$ , $H(n)$ never again lands on a whole number. I have seen this problem set in more than one Mathematics Olympiad paper, and its solution, a pretty piece of reasoning, is worth describing.

Missing the cracks

Suppose that $n>1$ . Choose an integer $k$ such that $2^ k \leq n \leq 2^{k+1}$ . Then $1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{2^ k} + \dots + \frac{1}{n} = H(n).$ Consider the lowest common multiple of $1, 2, 3, \dots , 2^ k-1, 2^ k+1, \ldots , n$ . This number will be of the form $P \times \ 2^{k-1}$ , where $P$ is an odd integer. Now multiply both sides of the equation by this number, to get

$P \times \ 2^{k-1} \left(1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{2^ k} + \dots + \frac{1}{n}\right) = P \times \ 2^{k-1} \times \ H(n).$

Now, when multiplied out, all the terms on the left will be integers, except one:

$P \times \ 2^{k-1} \times \ \frac{1}{2^ k} =\frac{P}{2}$

is not an integer, since $P$ is odd. So the left hand side is not an integer, and hence neither is the right hand side. That means that $H(n)$ is not an integer.

Record rainfalls

How often are weather records broken? The harmonic series gives the answer.

Suppose we have a list of rainfall figures for a hundred years. How many record-breaking falls of rain do you expect have taken place over that period? We assume that the rainfall figures are random, in the sense that the amount of rain in any one year has no influence on the rainfall in any subsequent year.

The first year was undoubtedly a record year. In the second year, the rain could equally likely have been more than, or less than, the rainfall of the first year. So there is a probability of $1/2$ that the second year was a record year. The expected number of record years in the first two years of record-keeping is therefore $1+1/2$ . Go on to the third year. The probability is 1/3 that the third observation is higher than the first two, so the expected number of record rainfalls in three years is $1+1/2+1/3$ . Continuing this line of reasoning leads to the conclusion that the expected number of records in the list of $n$ observations is

$1+1/2+1/3+ \dots +1/n.$

What was your guess for the number of record rainfalls in a hundred years of keeping rainfall figures? If it was 5, you were nearly right, for the sum of the first hundred terms of the harmonic series is 5.19.

Even after a record-breaking rainfall, nobody will deny that the record will be broken some time in the future - perhaps in the very next year. The number of record years in an infinity of observations is clearly infinity. There we have an intuitive reason for believing that the harmonic series diverges.

Athletic records do not follow the same pattern, since they are not random in the way rainfall records are random. Athletes are always trying to break the current record, and training methods are continually being improved. Nobody is doing anything about improving the weather.

For the record, in both senses, here are some values of $H(n)$ :

n	1	5	10	50	100	500	1000
H(n)	1	2.28	2.93	4.50	5.19	6.79	7.49

Traffic flow

Bunched Traffic

In single-lane traffic, with no overtaking, a slow car will be followed by a bunch of cars wanting to go faster, but unable to do so. If $n$ cars set out, how many bunches will form? That is the same as asking how many record low speeds will be observed, and we know the answer: $1+1/2+1/3+ \dots +1/n.$ Because the bunches are successively slower, they will be more widely spaced. This explains why cars near the exit of a long tunnel tend to travel faster and in smaller bunches more widely separated than cars near the entrance of the tunnel.

Testing to destruction

Suppose you have a hundred similar wooden beams and want to find their minimum breaking strain. You build a simple machine which applies a gradually increasing force $F$ to the centre of the beam while it is supported at its ends in a horizontal position. By increasing the force $F$ until the beam breaks, you can find the breaking strain of each beam. Suppose we denote the breaking strain of the $n$ th beam by $F_ n$ .

A test to destruction carried out in this way has one major disadvantage. At the end you know the precise value of $F_ n$ for every $n$ but have destroyed all the beams in the process. However, we did not actually want the precise value of $F_ n$ for every $n$ , only the minimum value of $F_ n$ , for $1 < n < 100$ . Instead of testing each beam to destruction, you proceed as follows.

Test the first beam to destruction, and record its breaking strain ( $F_1$ ). Now test the second beam, by gradually increasing the force $F$ up to $F_1$ , but no further. If the beam survives, you know that its breaking strain is more than $F_1$ . If it breaks, you record its breaking strain $F_2$ . Now test the third beam, increasing the force up to $F_1$ or $F_2$ , whichever is lower. If it breaks, record its breaking strain $F_3$ . If it survives, go on the next beam.

This procedure successively finds the record minimum breaking strains. Only beams with record low breaking strains are destroyed by the test. Out of one hundred beams, you expect to destroy 5.19 by this sequential testing to destruction. If you had a thousand beams to test, you would expect to destroy only 7.49.

Shuffling cards

Just about the simplest (mathematically speaking) way of shuffling cards is called the "Top in at random" shuffle. The top card of a card deck of $n$ cards is removed and inserted at random in the deck. How many times must this shuffle be repeated before we can regard the deck as "random"?

Let us follow the progress of the card which is initially at the bottom of the deck. This card (label it $B$ ) stays at the bottom until another card is inserted below it. Since there are $n$ places into which a card taken from the top can go, the chance that it will go below $B$ is $1/n$ , and therefore on average it will take $n$ "top in at random" shuffles before a card is placed below $B$ . Now the chance that a card taken from the top and inserted at random into the deck will go in below $B$ is $2/n$ since there are now two places below $B$ , and the expected number of shuffles needed to get a second card below $B$ is $n/2$ . Thus the expected number of shuffles needed to get two cards below $B$ is $n/2$ . Thus the expected number of shuffles needed to get two cards below $B$ is $n+n/2$ . Note that at this stage the cards below $B$ are in random order. Continuing in this way, we see that the expected number of "top in at random" shuffles needed to get $B$ up to the top of the deck is

$n + n/2 + n/3 + \dots + n/(n-1) = n[1 + 1/2 + 1/3 + \dots + 1/(n-1)].$

At this stage the cards below $B$ are in random order, and just one more shuffle, which puts $B$ at random into the deck, is needed to randomise the deck. The total number of shuffles needed is thus

$n + n/2 + n/3 + \dots + n/(n-1) = n[1 + 1/2 + 1/3 + \dots + 1/(n-1)+ 1/n] =nH(n).$

Crossing the desert

This little problem achieved a great deal of attention during the last war - so much so that it was rumoured to have been devised by the Germans and parachuted into Britain in order to distract British scientists from the war effort.

You have to cross the desert in a jeep. There are no sources of fuel in the desert, and you cannot carry enough fuel in the jeep in order to make the crossing in one go. You haven't the time to establish fuel dumps, but you do have a large supply of jeeps. How can you get across the desert, using the minimum amount of fuel?

Let us measure the distance a jeep can travel in terms of a tankful of fuel. One jeep by itself can travel a distance of one tankful. If two jeeps set out together, they travel for 1/3 of a tankful, then Jeep 2 transfers 1/3 of its tankful to Jeep 1, and returns to base on the remaining 1/3 tankful. Jeep 1 is then able to travel a total of 1+1/3 tankfuls.

With three jeeps, stop after travelling 1/5 of a tankful, and transfer 1/5 of a tankful from jeep 3 into each of Jeeps 1 and 2, which are now full. Jeep 3 now has 2/5 of a tankful, Jeeps 1 and 2 now proceed as before, with Jeep 2 returning with an empty tank to Jeep 3. Between them, they have enough fuel to get back to base. Meanwhile, Jeep 1 has travelled a total of 1+1/3+1/5 tankfuls.

The same reasoning shows that with four jeeps you can get a distance of 1+1/3+1/5+1/7 tankfuls, and with $n$ jeeps you can get a jeep across a desert which is

$1+1/3+1/5+ \dots + 1/(2n+1) \mbox{tankfuls wide.}$

Here we have a new series, which is also harmonic (the reciprocals are in arithmetic progression), and also diverges, for clearly

$1+1/3+1/5+ \dots + 1/(2n+1) > \frac{1}{2}\left( 1+1/2+1/3+ \dots + 1/n \right) .$

The fact that the series diverges shows that, by using the system of transferring fuel, you can effect a crossing of arbitrary length, as long as you have enough jeeps. One might add: as long as the desert is wide enough to accommodate all those jeeps!

Other series

We have just seen that the series $1+1/3+1/5+ \dots$ which is obtained from the original harmonic series by deleting every second term, still diverges. What about the series

$1/2 + 1/3 + 1/5 + 1/7 + \dots$

where the first term and all terms with composite (non-prime) denominators have been deleted? Since the remaining denominators are all prime, and the prime numbers are very thinly scattered, it is indeed surprising that the series of reciprocals of primes still diverges.

The proof of this fact is a little too complicated to give here (although it's only first-year university level) so I'll leave you to try to discover it yourself. When you've proved that this series diverges, you can deduce as a corollary that there are infinitely many prime numbers, though there is a simpler way of proving this fact.

Instead of deleting all terms with composite denominators, let's delete every term which has a zero in its denominator. It looks as though one is deleting roughly one in ten of the terms of the original harmonic series. Thus it seems a reasonable guess that the leftover series diverges, and it may be a shock to your intuition to learn that your guess is wrong.

Let us look first at all terms of the leftover series with just one digit in the denominator. There are exactly 9 of these, and they are all less than 1. Their sum is thus less than 9.

Next, look at the terms of this series with exactly two digits in their denominator. There are 81 of these, all less than 1/10. Their sum is less than $9^2/10$ .

In general, there are $9^ k$ terms of the series with exactly $k$ digits in the denominator, and each is less than $1/10^{k-1}$ . Their total is thus less than $9^ k/10^{k-1}$ . Thus the sum of the terms in the series is less than

$9 \left[1 + 9/10 + (9/10)^2 + (9/10)^3 + \dots \right]$

which is a geometric series whose sum to infinity is 90. Thus the harmonic series without the terms containing zero digits converges. A more careful analysis can be given to show that the sum of this series is 23.10345, to five decimal places.

The logarithmic connection

Let us now go back to Oresme's proof that the harmonic series diverges, which was achieved by showing that $H(2^ n) \geq (n+2)/2$ . This inequality suggests a logarithmic connection.

Your will recall that Pythagoras noticed that the note emitted by a plucked string rose by an interval of a fifth if the string was reduced to 2/3 of its length. He also noted that the interval of a fourth was obtained by reducing the string to 3/4 of its length. The difference between a fourth and a fifth is a tone, whose ratio (8/9) is obtained by dividing 2/3 by 3/4. That is probably the earliest manifestation of a logarithmic law.

The link between the harmonic series and logarithms is even more intimate. A more careful analysis of Oresme's inequality, which requires a little calculus, shows that $H(n)$ increases at the same rate as $\log _ e n$ , the natural logarithm of $n$ . The analysis shows that the difference

$\log _ e n - H(n)$

converges to a constant value, usually denoted by $\gamma$ , as $n$ tends to infinity. This is Euler's constant, named after the famous Swiss mathematician Leonard Euler. The value of $\gamma$ has been calculated to be approximately 0.577, but very little is known about the nature of $\gamma$ . It is not even known whether $\gamma$ is rational or irrational. Instant fame awaits you if you can resolve this famous unsolved problem.

About the author

John H. Webb was born in Cape Town and studied mathematics at the University of Cape Town. He won a scholarship to Cambridge where he obtained a Ph D. Back at the University of Cape Town, his career as a research mathematician was eventually overtaken by interests in mathematics education, with particular emphasis on popularising mathematics and identifying and stimulating promising students.

He edits Mathematical Digest, a quarterly magazine for high schools, runs a maths competition for schools in the Cape Town area, and directs a nationwide Mathematical Talent Search, a problem-solving programme by correspondence which selects and trains South African teams for the International Mathematical Olympiad.

He is at present on sabbatical leave, and is spending six months working with the Millennium Mathematics Project in Cambridge. His visit is supported by the Institute of Actuaries.

Comments

Thanks!

Thanks for the informative and well-organized post! As a first year university student, I've been mesmerized by the fact that the harmonic series diverges whereas the p-series with p>1 actually converges! This was a great explanation for the former.

Thanks a lot!

Very beautiful and useful article with amazing pictures.

thanks

beautiful article but the exercise of the desert doesn't it need to be
1+1/3+1/5+...+1/(2n-1) tankfuls wide

Record rainfalls

In the rainfalls example, why don't you say in the third year (and any year thereafter) the rain could equally likely have been more than, or less than, the rainfall of the record year so far. So there always is a probability of 1/2 that any year was a record year.?