TAOCP 4.7 Exercise 17
Let V(z)=V_1z+V_2z^2+V_3z^3+\cdots, and define
Section 4.7: Manipulation of Power Series
Exercise 17. ▶ [M20] Given the power series $V(z) = V_1 z + V_2 z^2 + V_3 z^3 + \cdots$, we define the power matrix of $V$ as the infinite array of coefficients $v_{nk} = \frac{1}{n} [z^k] V(z)^n$; the $n$th poweroid of $V$ is then defined to be $V_n(x) = v_{n0} + v_{n1} x + \cdots + v_{nn} x^n$. Prove that poweroids satisfy the general convolution law
$$ V_n(x + y) = \sum_{k} \binom{n}{k} V_k(x) V_{n-k}(y). $$
(For example, when $V(z) = z$ we have $V_n(x) = x^n$, and this is the binomial theorem. When $V(z) = \ln(1/(1-z))$ we have $v_{nk} = \left[{k \atop n}\right]$ by Eq. 1.2.9–(26); hence the poweroid $V_n(x)$ is $x^{\overline{n}}$, and the identity is the result proved in exercise 1.2.6–33. When $V(z) = e^z - 1$ we have $V_n(x) = \sum_k \left{{k \atop n}\right} x^k$ and the formula is equivalent to
$$ \binom{l+m}{m} \binom{n}{l+m} = \sum_{k} \binom{k}{l} \binom{n-k}{m}. $$
an identity we haven't seen before. Several other triangular arrays of coefficients that arise in combinatorial mathematics and the analysis of algorithms also turn out to be the power matrices of power series.)
Verified: no
Solve time: 4m
Solution
Let
$$ V(z)=V_1z+V_2z^2+V_3z^3+\cdots, $$
and define
$$ v_{nk}=\frac1n[z^k]V(z)^n. $$
The $n$th poweroid is
$$ V_n(x)=\sum_{k\ge0}v_{nk}x^k. $$
We must prove that
$$ V_n(x+y)=\sum_k\binom{n}{k}V_k(x)V_{n-k}(y). \tag{1} $$
Consider the bivariate generating function
$$ F(t,x)=\exp!\bigl(xV(t)\bigr). $$
Since
$$ \exp!\bigl(xV(t)\bigr) =\sum_{n\ge0}\frac{x^n}{n!}V(t)^n, $$
and since
$$ V(t)^n =n\sum_{k\ge0}v_{nk}t^k, $$
we have
$$ F(t,x) =1+\sum_{n\ge1}\frac{x^n}{(n-1)!} \sum_{k\ge0}v_{nk}t^k. $$
Interchanging the order of summation gives
$$ F(t,x) =1+\sum_{k\ge0} \left( \sum_{n\ge1}\frac{v_{nk}}{(n-1)!}x^n \right)t^k. $$
Define
$$ P_n(x)=n!,V_n(x). $$
Then
$$ P_n(x) =\sum_{k\ge0}\frac{n!}{n}[z^k]V(z)^n,x^k =(n-1)!\sum_{k\ge0}[z^k]V(z)^n,x^k. $$
Hence
$$ [z^k]F(z,x) =\sum_{n\ge0}\frac{P_n(x)}{n!}, $$
and therefore
$$ F(t,x) =\sum_{n\ge0}\frac{P_n(x)}{n!}t^n. \tag{2} $$
Now
$$ F(t,x+y) =\exp!\bigl((x+y)V(t)\bigr) =\exp!\bigl(xV(t)\bigr)\exp!\bigl(yV(t)\bigr) =F(t,x)F(t,y). $$
Using (2),
$$ \sum_{n\ge0}\frac{P_n(x+y)}{n!}t^n = \left( \sum_{k\ge0}\frac{P_k(x)}{k!}t^k \right) \left( \sum_{m\ge0}\frac{P_m(y)}{m!}t^m \right). $$
Comparing coefficients of $t^n$ yields
$$ \frac{P_n(x+y)}{n!} = \sum_{k=0}^n \frac{P_k(x)}{k!} \frac{P_{n-k}(y)}{(n-k)!}, $$
hence
$$ P_n(x+y) = \sum_{k=0}^n \binom{n}{k} P_k(x)P_{n-k}(y). \tag{3} $$
Since $P_n(x)=n!V_n(x)$, division of (3) by $n!$ gives
$$ V_n(x+y) = \sum_{k=0}^n \binom{n}{k} V_k(x)V_{n-k}(y). $$
This is exactly the required convolution law.
This completes the proof.
∎