TAOCP 1.2.7 Exercise 22
Let S_n=\sum_{k=0}^{n} H_kH_{n-k}.
Section 1.2.7: Harmonic Numbers
Exercise 22. [M28] Evaluate $\sum_{k=0}^{n} H_k H_{n-k}$.
Verified: no
Solve time: -
Setup
Let
$$ S_n=\sum_{k=0}^{n} H_kH_{n-k}. $$
Since $H_0=0$, the terms with $k=0$ and $k=n$ vanish, hence
$$ S_n=\sum_{k=1}^{n-1}H_kH_{n-k}. $$
The problem is to evaluate $S_n$ in closed form.
We will prove that
$$ S_n=(n+1)\bigl(H_n^2-H_n^{(2)}\bigr)-2nH_n+2n, $$
where
$$ H_n^{(2)}=\sum_{j=1}^{n}\frac{1}{j^2}. $$
Solution
Expand one harmonic number:
$$ H_{n-k}=H_n-\sum_{j=n-k+1}^{n}\frac{1}{j}. $$
Therefore
$$ S_n =\sum_{k=0}^{n}H_k \left( H_n-\sum_{j=n-k+1}^{n}\frac{1}{j} \right). $$
Distributing the sum gives
$$ S_n = H_n\sum_{k=0}^{n}H_k - \sum_{k=0}^{n} H_k \sum_{j=n-k+1}^{n}\frac{1}{j}. $$
By equation (8),
$$ \sum_{k=0}^{n}H_k = \sum_{k=1}^{n}H_k = (n+1)H_n-n. $$
Hence the first term equals
$$ H_n\sum_{k=0}^{n}H_k = (n+1)H_n^2-nH_n. $$
For the second term, change the inner index by writing $j=n-r$, where $r=0,1,\ldots,k-1$:
$$ \sum_{j=n-k+1}^{n}\frac{1}{j} = \sum_{r=0}^{k-1}\frac{1}{n-r}. $$
Interchanging summation,
$$ \sum_{k=0}^{n} H_k \sum_{r=0}^{k-1}\frac{1}{n-r} = \sum_{r=0}^{n-1} \frac{1}{n-r} \sum_{k=r+1}^{n}H_k. $$
Set $m=n-r$. Then $m$ runs from $1$ to $n$, and
$$ \sum_{k=r+1}^{n}H_k = \sum_{k=n-m+1}^{n}H_k. $$
By equation (8),
$$ \sum_{k=1}^{n}H_k=(n+1)H_n-n, $$
and
$$ \sum_{k=1}^{n-m}H_k = (n-m+1)H_{n-m}-(n-m). $$
Thus
$$ \sum_{k=n-m+1}^{n}H_k = (n+1)H_n-n - \bigl((n-m+1)H_{n-m}-(n-m)\bigr), $$
which simplifies to
$$ \sum_{k=n-m+1}^{n}H_k = (n+1)H_n-(n-m+1)H_{n-m}-m. $$
Therefore the second term is
$$ \sum_{m=1}^{n} \frac{1}{m} \Bigl( (n+1)H_n-(n-m+1)H_{n-m}-m \Bigr). $$
Separate the sums:
$$= (n+1)H_n\sum_{m=1}^{n}\frac{1}{m} - \sum_{m=1}^{n} \frac{n-m+1}{m}H_{n-m} - \sum_{m=1}^{n}1.$$
Since $\sum_{m=1}^{n}1=n$ and $\sum_{m=1}^{n}1/m=H_n$, this becomes
$$ (n+1)H_n^2 - \sum_{m=1}^{n} \frac{n-m+1}{m}H_{n-m} - n. $$
Substitute $t=n-m$:
$$ \sum_{m=1}^{n} \frac{n-m+1}{m}H_{n-m} = \sum_{t=0}^{n-1} \frac{t+1}{n-t}H_t. $$
Now write
$$ \frac{t+1}{n-t} = \frac{n+1}{n-t}-1. $$
Hence
$$ \sum_{t=0}^{n-1} \frac{t+1}{n-t}H_t = (n+1) \sum_{t=0}^{n-1} \frac{H_t}{n-t} - \sum_{t=0}^{n-1}H_t. $$
Exercise 21 gives
$$ \sum_{t=1}^{n}\frac{H_t}{n+1-t} = H_{n+1}^2-H_{n+1}^{(2)}. $$
Replacing $n$ by $n-1$,
$$ \sum_{t=1}^{n-1}\frac{H_t}{n-t} = H_n^2-H_n^{(2)}. $$
Also, by equation (8),
$$ \sum_{t=0}^{n-1}H_t = nH_{n-1}-(n-1). $$
Thus the second term equals
$$ (n+1)H_n^2 - (n+1)\bigl(H_n^2-H_n^{(2)}\bigr) + nH_{n-1} -(n-1) - n. $$
Since
$$ H_{n-1}=H_n-\frac{1}{n}, $$
this simplifies to
$$ (n+1)H_n^{(2)} + nH_n -2n. $$
Combining with the first term,
$$ S_n = \bigl((n+1)H_n^2-nH_n\bigr) - \bigl((n+1)H_n^{(2)}+nH_n-2n\bigr). $$
Therefore
$$ S_n = (n+1)\bigl(H_n^2-H_n^{(2)}\bigr) -2nH_n +2n. $$
Thus
$$ \boxed{ \sum_{k=0}^{n}H_kH_{n-k} = (n+1)\bigl(H_n^2-H_n^{(2)}\bigr) -2nH_n+2n }. $$
Verification
Take $n=2$.
Direct computation gives
$$ H_0H_2+H_1H_1+H_2H_0 = 0+1+0 = 1. $$
The formula gives
$$ (3)\left(\left(\frac32\right)^2-\left(1+\frac14\right)\right) -4\cdot\frac32+4. $$
Since
$$ \left(\frac32\right)^2-\frac54 = 1, $$
the value is
$$ 3-6+4=1. $$
Take $n=3$.
Direct computation gives
$$ H_1H_2+H_2H_1 = 2\cdot\frac32 = 3. $$
The formula gives
$$ 4\left( \left(\frac{11}{6}\right)^2 - \left(1+\frac14+\frac19\right) \right) - 6\cdot\frac{11}{6} + 6. $$
Since
$$ \left(\frac{11}{6}\right)^2-\frac{49}{36} = 2, $$
the value is
$$ 8-11+6=3. $$
The evaluations agree.
Notes
A generating-function method also yields the result. Since
$$ \sum_{n\ge0}H_nx^n = \frac{\ln(1/(1-x))}{1-x}, $$
the required sum is the coefficient of $x^n$ in
$$ \left( \frac{\ln(1/(1-x))}{1-x} \right)^2. $$
The coefficient extraction reduces to the same harmonic-number expression above.