TAOCP 1.2.7 Exercise 11

Exercise 11. [M21] Using summation by parts, evaluate

$$ \sum_{1<k \le n}\frac{1}{k(k-1)}H_k. $$

Verified: yes
Solve time: 1m14s

Solution

Let

$$ S=\sum_{1<k\le n}\frac{1}{k(k-1)}H_k. $$

To apply summation by parts in the form of Exercise 10, choose

$$ a_k=-\frac1{k-1}\qquad (k\ge2), $$

so that

$$ a_{k+1}-a_k =-\frac1k+\frac1{k-1} =\frac1{k(k-1)}. $$

Also take

$$ b_k=H_k. $$

Then

$$ S=\sum_{1<k\le n}(a_{k+1}-a_k)b_k =\sum_{2\le k\le n}(a_{k+1}-a_k)b_k. $$

Applying the summation-by-parts formula with indices $2\le k\le n$ gives

$$ S=a_{n+1}H_n-a_2H_1 -\sum_{2\le k\le n}a_{k+1}(H_{k+1}-H_k). $$

Since

$$ a_{n+1}=-\frac1n,\qquad a_2=-1,\qquad H_1=1, $$

and

$$ H_{k+1}-H_k=\frac1{k+1}, $$

we obtain

$$ S=-\frac{H_n}{n}+1 +\sum_{2\le k\le n}\frac1k\frac1{k+1}. $$

The remaining sum is

$$ \sum_{k=2}^{n}\frac1{k(k+1)} =\sum_{k=2}^{n}\left(\frac1k-\frac1{k+1}\right) =\frac12-\frac1{n+1}. $$

Therefore

$$ S =1-\frac{H_n}{n} +\frac12-\frac1{n+1} =\frac32-\frac1{n+1}-\frac{H_n}{n}. $$

Hence

$$ \boxed{\sum_{1<k\le n}\frac{1}{k(k-1)}H_k =\frac32-\frac1{n+1}-\frac{H_n}{n}}. $$