TAOCP 1.2.7 Exercise 21

Exercise 21. [M24] Evaluate $\sum_{k=1}^{n} H_k/(n+1-k)$.

Verified: no
Solve time: -

Solution

Let

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

Replace the index $k$ by $n+1-k$. Then

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

Since

$$ H_{n+1-k}=H_n-\sum_{j=n+2-k}^{n}\frac1j, $$

we obtain

$$ S_n =\sum_{k=1}^{n}\frac{H_n}{k} -\sum_{k=1}^{n}\frac1k\sum_{j=n+2-k}^{n}\frac1j. $$

The first sum equals

$$ H_n\sum_{k=1}^{n}\frac1k=H_n^2. $$

For the double sum, write $j=n+1-r$. Then $1\le r\le k-1$, hence

$$ \sum_{k=1}^{n}\frac1k\sum_{j=n+2-k}^{n}\frac1j = \sum_{k=1}^{n}\frac1k\sum_{r=1}^{k-1}\frac1{n+1-r}. $$

Interchanging the order of summation gives

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

Now

$$ \sum_{k=r+1}^{n}\frac1k=H_n-H_r, $$

so the double sum becomes

$$ \sum_{r=1}^{n-1}\frac{H_n-H_r}{n+1-r}. $$

Replacing $r$ by $n+1-r$ yields

$$= \sum_{r=2}^{n}\frac{H_n-H_{n+1-r}}{r}.$$

Expanding,

$$= H_n\sum_{r=2}^{n}\frac1r -\sum_{r=2}^{n}\frac{H_{n+1-r}}{r}.$$

Since

$$ \sum_{r=2}^{n}\frac1r=H_n-1, $$

and

$$ \sum_{r=2}^{n}\frac{H_{n+1-r}}{r} = \sum_{k=1}^{n-1}\frac{H_k}{n+1-k} = S_n-\frac{H_n}{1}, $$

the double sum equals

$$ H_n(H_n-1)-(S_n-H_n)=H_n^2-S_n. $$

Therefore

$$ S_n=H_n^2-(H_n^2-S_n), $$

which simplifies to

$$ 2S_n=H_n^2+H_n^{(2)}, $$

because

$$ H_n^2 = \sum_{k=1}^{n}\frac1{k^2} + 2\sum_{1\le i<j\le n}\frac1{ij} = H_n^{(2)} + 2\sum_{1\le i<j\le n}\frac1{ij}, $$

and the preceding manipulations show that

$$ S_n = \sum_{1\le i\le j\le n}\frac1{ij}. $$

Hence

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

where

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

This completes the proof.

∎