TAOCP 1.2.9 Exercise 6

Let us denote the sequence in question by a_n = \sum_{0<k<n} \frac{1}{k(n-k)}, \qquad n \ge 2, and $a_0=a_1=0$.

taocpmathematicsalgorithmsvolume-1hm-simple

Section 1.2.9: Generating Functions

Exercise 6. [HM15] Find the generating function for

$$ \left\langle \sum_{0<k<n} \frac{1}{k(n-k)} \right\rangle; $$

differentiate it and express the coefficients in terms of harmonic numbers.

Verified: no
Solve time: -

Solution

Let us denote the sequence in question by

$$ a_n = \sum_{0<k<n} \frac{1}{k(n-k)}, \qquad n \ge 2, $$

and $a_0=a_1=0$. We first simplify the general term. Observe that

$$ \frac{1}{k(n-k)} = \frac{1}{n} \left( \frac{1}{k} + \frac{1}{n-k} \right). $$

Hence, for $n \ge 2$,

$$ a_n = \sum_{k=1}^{n-1} \frac{1}{k(n-k)} = \frac{1}{n} \sum_{k=1}^{n-1} \left( \frac{1}{k} + \frac{1}{n-k} \right) = \frac{1}{n} \sum_{k=1}^{n-1} \frac{1}{k} + \frac{1}{n} \sum_{k=1}^{n-1} \frac{1}{n-k}. $$

Reindexing the second sum by $j = n-k$ gives

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

Thus

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

where $H_m = \sum_{k=1}^{m} \frac{1}{k}$ is the $m$th harmonic number.

By equation (18), the generating function for the harmonic numbers $\langle H_n \rangle$ is

$$ \sum_{n \ge 0} H_n z^n = \frac{1}{1-z} \ln \frac{1}{1-z}. $$

Shifting indices, we have

$$ \sum_{n \ge 1} H_{n-1} z^n = z \sum_{n \ge 1} H_{n-1} z^{n-1} = z \sum_{m \ge 0} H_m z^m = z \frac{1}{1-z} \ln \frac{1}{1-z}. $$

Multiplying each term by $2/n$ to match $a_n = 2 H_{n-1}/n$ corresponds to integrating term-by-term:

$$ \sum_{n \ge 1} a_n z^n = \sum_{n \ge 1} \frac{2 H_{n-1}}{n} z^n = 2 \sum_{n \ge 1} \frac{H_{n-1}}{n} z^n = 2 \int_0^z \sum_{n \ge 1} H_{n-1} t^{n-1} , dt. $$

Substituting the previous generating function gives

$$ \sum_{n \ge 1} a_n z^n = 2 \int_0^z \frac{1}{1-t} \ln \frac{1}{1-t} , dt. $$

Differentiating both sides, we find

$$ \frac{d}{dz} \sum_{n \ge 1} a_n z^n = \sum_{n \ge 1} n a_n z^{n-1} = \sum_{n \ge 1} 2 H_{n-1} z^{n-1}. $$

Replacing $n-1$ by $k$ yields

$$ \sum_{n \ge 1} n a_n z^{n-1} = 2 \sum_{k \ge 0} H_k z^k = \frac{2}{1-z} \ln \frac{1}{1-z}. $$

Thus the generating function for the sequence $n a_n = 2 H_{n-1}$ is

$$ \sum_{n \ge 1} n a_n z^{n-1} = \frac{2}{1-z} \ln \frac{1}{1-z}. $$

This completes the proof. ∎

$$ \boxed{\sum_{n \ge 1} a_n z^n = 2 \int_0^z \frac{\ln \frac{1}{1-t}}{1-t} , dt, \qquad \sum_{n \ge 1} n a_n z^{n-1} = \frac{2}{1-z} \ln \frac{1}{1-z}} $$