So... this is the explanation my instructor gives in his PDF, but I can't make heads or tails of it.
Use mathematical induction to prove that for all positive integers n:
H1 + H2 + . . . + Hn = (n + 1)Hn − n.
solution: The base case is easy. For the induction step we assume H1+H2+. . .+Hk = (k+1)Hk−k
for arbitrary positive integer k. Then
H1 + H2 + . . . + Hk+1 = (k + 1)Hk − k + Hk+1
= $\frac{(k + 1)*H_{k+1} − (k + 1)}{(k + 1) − k + H_{k+1}}$
= (k + 2)Hk+1 − (k + 1)
Why is there the division in the second step? I've been trying to solve this by doing:
$$(k+1)\frac{1}{k}-k + \frac{1}{k+1} == (k+2)\frac{1}{k+1} - (k+1)$$
but can't seem to make the two equal. So some explanation of his proof or some description of the faults in my methodology would be sincerely appreciated.
Observe that: $$ (k+1)(H_k)=(k+1)\left(H_{k+1}-\frac{1}{k+1}\right)=(k+1)H_{k+1}-\frac{k+1}{k+1}=(k+1)H_{k+1}-1. $$ And so $$ (k+1)H_k-k+H_{k+1}=(k+1)H_{k+1}-1-k+H_{k+1}=(k+2)H_{k+1}-(k+1). $$