Quandaries
and Queries
I am a high school teacher (9-12) and have this question about
induction.
Harmonic numbers are Hn = 1 + 1/2 + 1/3 + . . . + 1/n
Use induction to prove the following theorem:
For all natural numbers n, H1 + H2 + . . . + Hn = (1+n)Hn - n
Thank you
Becky
Hi Becky,
First verify that the expression is true when n=1.
Notice that the defining relation, Hn = 1 + 1/2 + 1/3 + . . . + 1/n, can be written Hn+1=Hn+1/(n+1), or equivalently Hn=Hn+1-1/(n+1).
For the induction step, assume that H1 + H2 + . . . + Hn = (1+n)Hn - n is true for n=1,2,...,k. We need to show that H1 + H2 + . . . + Hk+1 = (2+k)Hk - ( k+1).
H1 + H2 + . . . + Hk+1
= (H1 + H2 + . . . + Hk) + Hk+1
= ((1+k)Hk -k) + Hk+1
= (1+k)(Hk+1 - 1/(k+1)) - k + Hk+1
= (1+k)Hk+1 - 1 - k + Hk+1
= (2+k)Hk+1 - (1+k)
Cheers,
Penny