TAOCP 1.2.7 Exercise 14

Exercise 14. [M22] Show that

$$ \sum_{k=1}^{n}\frac{H_k}{k} = \frac{1}{2}(H_n^2 + H_n^{(2)}), $$

and evaluate $\sum_{k=1}^{n} H_k/(k+1)$.

Verified: no
Solve time: -

Solution

Write

$$ S_n=\sum_{k=1}^{n}\frac{H_k}{k}. $$

Since

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

we have

$$ \frac{H_k}{k}=\frac{H_{k-1}}{k}+\frac1{k^2}. $$

Therefore

$$ S_n=\sum_{k=1}^{n}\frac{H_{k-1}}{k}+\sum_{k=1}^{n}\frac1{k^2}. $$

The second sum is

$$ \sum_{k=1}^{n}\frac1{k^2}=H_n^{(2)}. $$

For the first sum,

$$ \sum_{k=1}^{n}\frac{H_{k-1}}{k} =\sum_{k=1}^{n}\sum_{j=1}^{k-1}\frac1{jk}. $$

Interchanging the order of summation gives

$$ \sum_{k=1}^{n}\sum_{j=1}^{k-1}\frac1{jk} =\sum_{1\le j<k\le n}\frac1{jk}. $$

Now

$$ H_n^2 =\left(\sum_{k=1}^{n}\frac1k\right)^2 =\sum_{k=1}^{n}\frac1{k^2} +2\sum_{1\le j<k\le n}\frac1{jk}. $$

Hence

$$ \sum_{1\le j<k\le n}\frac1{jk} =\frac12\left(H_n^2-H_n^{(2)}\right). $$

Substituting into the expression for $S_n$ yields

$$ S_n =\frac12\left(H_n^2-H_n^{(2)}\right)+H_n^{(2)} =\frac12\left(H_n^2+H_n^{(2)}\right). $$

Therefore

$$ \boxed{\sum_{k=1}^{n}\frac{H_k}{k} =\frac12\left(H_n^2+H_n^{(2)}\right)}. $$

Now evaluate

$$ \sum_{k=1}^{n}\frac{H_k}{k+1}. $$

Using

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

we obtain

$$ \sum_{k=1}^{n}\frac{H_k}{k+1} =\sum_{k=1}^{n}\frac{H_{k+1}}{k+1} -\sum_{k=1}^{n}\frac1{(k+1)^2}. $$

Replacing $k+1$ by $j$,

$$ \sum_{k=1}^{n}\frac{H_{k+1}}{k+1} =\sum_{j=2}^{n+1}\frac{H_j}{j}. $$

Applying the first result,

$$ \sum_{j=1}^{n+1}\frac{H_j}{j} =\frac12\left(H_{n+1}^2+H_{n+1}^{(2)}\right). $$

Hence

$$ \sum_{j=2}^{n+1}\frac{H_j}{j} =\frac12\left(H_{n+1}^2+H_{n+1}^{(2)}\right)-1, $$

since $H_1=1$ and $H_1^{(2)}=1$.

Also,

$$ \sum_{k=1}^{n}\frac1{(k+1)^2} =\sum_{j=2}^{n+1}\frac1{j^2} =H_{n+1}^{(2)}-1. $$

Therefore

$$ \sum_{k=1}^{n}\frac{H_k}{k+1} =\frac12\left(H_{n+1}^2+H_{n+1}^{(2)}\right)-1-\left(H_{n+1}^{(2)}-1\right), $$

which simplifies to

$$ \boxed{\sum_{k=1}^{n}\frac{H_k}{k+1} =\frac12\left(H_{n+1}^2-H_{n+1}^{(2)}\right)}. $$

∎