TAOCP 1.2.9 Exercise 2

Exercise 2. [M13] Prove Eq. (11).

Verified: no
Solve time: -

Solution

We are asked to prove equation (11):

$$ \left(\frac{a_0}{0!}+\frac{a_1}{1!}z+\frac{a_2}{2!}z^2+\cdots\right) \left(\frac{b_0}{0!}+\frac{b_1}{1!}z+\frac{b_2}{2!}z^2+\cdots\right) = \left(\frac{c_0}{0!}+\frac{c_1}{1!}z+\frac{c_2}{2!}z^2+\cdots\right), $$

where $c_n = \sum_k \binom{n}{k} a_k b_{n-k}$.

Let

$$ A(z) = \sum_{k \ge 0} \frac{a_k}{k!} z^k, \qquad B(z) = \sum_{k \ge 0} \frac{b_k}{k!} z^k. $$

The product $A(z)B(z)$ is then

$$ A(z)B(z) = \sum_{i \ge 0} \sum_{j \ge 0} \frac{a_i}{i!} \frac{b_j}{j!} z^{i+j}. $$

We now collect terms with the same power of $z$. Fix $n \ge 0$. The coefficient of $z^n$ is

$$ \sum_{i+j=n} \frac{a_i}{i!}\frac{b_j}{j!}. $$

Setting $i=k$ and $j=n-k$, we obtain

$$ \sum_{k=0}^{n} \frac{a_k}{k!} \frac{b_{n-k}}{(n-k)!}. $$

Factor $1/n!$ from each term:

$$ \sum_{k=0}^{n} \frac{a_k b_{n-k}}{k!(n-k)!} = \frac{1}{n!} \sum_{k=0}^{n} \binom{n}{k} a_k b_{n-k}. $$

By the definition of $c_n$, this equals $c_n/n!$. Hence the product series becomes

$$ A(z)B(z) = \sum_{n \ge 0} \frac{c_n}{n!} z^n, $$

as required. This completes the proof.

∎