We will use mathematical induction on n, the harmonic sum subscript.
The induction will consist of two steps:
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.)
Source: The harmonic sum and a surprising inductive property (document since taken down), by Doug Hensley
Spot the fallacious step in this "proof" by induction that all people in Canada are the same age!