TAOCP 1.2.7 Exercise 15

Exercise 15. [M23] Express $\sum_{k=1}^{n} H_k^2$ in terms of $n$ and $H_n$.

Verified: no
Solve time: -

Solution

Let

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

We apply summation by parts in the same manner as the derivation of equation (9). Since

$$ 1=(k+1)-k, $$

we have

$$ H_k^2=(k+1)H_k^2-kH_k^2. $$

Using

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

it follows that

$$ (k+1)H_k^2 =(k+1)\left(H_{k+1}-\frac1{k+1}\right)^2 =(k+1)H_{k+1}^2-2H_{k+1}+\frac1{k+1}. $$

Hence

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

Summing from $k=1$ to $n$ gives

$$ S_n =\sum_{k=1}^{n}\bigl((k+1)H_{k+1}^2-kH_k^2\bigr) -2\sum_{k=1}^{n}H_{k+1} +\sum_{k=1}^{n}\frac1{k+1}. $$

The first sum telescopes:

$$ \sum_{k=1}^{n}\bigl((k+1)H_{k+1}^2-kH_k^2\bigr) =(n+1)H_{n+1}^2-H_1^2. $$

Since $H_1=1$,

$$ \sum_{k=1}^{n}\bigl((k+1)H_{k+1}^2-kH_k^2\bigr) =(n+1)H_{n+1}^2-1. $$

Also,

$$ \sum_{k=1}^{n}H_{k+1} =\sum_{k=1}^{n+1}H_k-H_1. $$

By equation (8),

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

therefore

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

Finally,

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

Substituting these results,

$$ \begin{aligned} S_n &=(n+1)H_{n+1}^2-1 -2\bigl((n+2)H_{n+1}-(n+2)\bigr) +H_{n+1}-1 \ &=(n+1)H_{n+1}^2-(2n+3)H_{n+1}+2n+2. \end{aligned} $$

Since

$$ H_{n+1}=H_n+\frac1{n+1}, $$

we obtain

$$ (n+1)H_{n+1}^2 =(n+1)H_n^2+2H_n+\frac1{n+1}, $$

and

$$ (2n+3)H_{n+1} =(2n+3)H_n+\frac{2n+3}{n+1}. $$

Hence

$$ \begin{aligned} S_n &=(n+1)H_n^2-(2n+1)H_n +\frac1{n+1}-\frac{2n+3}{n+1}+2n+2 \ &=(n+1)H_n^2-(2n+1)H_n+2n. \end{aligned} $$

Therefore

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

Thus

$$ \boxed{\sum_{k=1}^{n}H_k^2=(n+1)H_n^2-(2n+1)H_n+2n}. $$