Skip to main content.

Solution to puzzle 33: Harmonic sum

Skip restatement of puzzle.Let H0 = 0 and Hn = 1/1 + 1/2 + ... + 1/n.
Show that, for n > 0, Hn = 1 + (H0 + H1 + ... + Hn−1)/n.

We will use mathematical induction on n, the harmonic sum subscript.

The induction will consist of two steps:

  1. Basis: Show the proposition is true for H1.
  2. Induction step: Prove that if the proposition is true for some arbitrary value, k > 0, then it holds for k+1.

The basis is straightforward.
We simply verify that H1 = 1 + H0/1, which is indeed the case.

For the induction step, we assume the inductive hypothesis:  Hk = 1 + (H0 + ... + Hk−1)/k.
It will be convenient below to write this as  kHk = k + H0 + H1 + ... + Hk−1.

By definition, Hk+1 = Hk + 1/(k+1)
  = [(k + 1)Hk + 1]/(k + 1)
  = (kHk + Hk + 1)/(k + 1)
By the inductive hypothesis, Hk+1 = (k + H0 + H1 + ... + Hk−1 + Hk + 1)/(k + 1)
  = 1 + (H0 + H1 + ... + Hk)/(k + 1)

This concludes the induction step: we have proved that the proposition holds for k + 1.

Therefore, for n > 0, Hn = 1 + (H0 + H1 + ... + Hn−1)/n.)

Further reading

  1. Concrete Mathematics: A Foundation for Computer Science (2nd Edition), by Ronald Graham, Oren Patashnik, Donald Ervin Knuth
    • Chapter 6.3: Harmonic Numbers
    • Chapter 6.4: Harmonic Summation
  2. The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd Edition), by Donald E. Knuth
    • Chapter 1.2.7: Harmonic Numbers

Source: (Adobe) Portable Document Format The harmonic sum and a surprising inductive property (document since taken down), by Doug Hensley

All people in Canada are the same age

Spot the fallacious step in this "proof" by induction that all people in Canada are the same age!

Back to top