# Solution to puzzle 33: Harmonic sum

Let H_{0} = 0 and H_{n} = 1/1 + 1/2 + ... + 1/n.

Show that, for n > 0, H_{n} = 1 + (H_{0} + H_{1} + ... + H_{n−1})/n.

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

The induction will consist of two steps:

- Basis: Show the proposition is true for H
_{1}.
- 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 H_{1} = 1 + H_{0}/1, which is indeed the case.

For the induction step, we assume the inductive hypothesis: H_{k} = 1 + (H_{0} + ... + H_{k−1})/k.

It will be convenient below to write this as kH_{k} = k + H_{0} + H_{1} + ... + H_{k−1}.

By definition, H_{k+1} | = H_{k} + 1/(k+1) |

| = [(k + 1)H_{k} + 1]/(k + 1) |

| = (kH_{k} + H_{k} + 1)/(k + 1) |

By the inductive hypothesis, H_{k+1} | = (k + H_{0} + H_{1} + ... + H_{k−1} + H_{k} + 1)/(k + 1) |

| = 1 + (H_{0} + H_{1} + ... + H_{k})/(k + 1) |

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

Therefore, for n > 0, H_{n} = 1 + (H_{0} + H_{1} + ... + H_{n−1})/n.)

## Further reading

- 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

- The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd Edition), by Donald E. Knuth
- Chapter 1.2.7: Harmonic Numbers

Source: 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