TAOCP 4.7 Exercise 21
The proposed solution does not correctly prove the stated matrix-product formula.
Section 4.7: Manipulation of Power Series
Exercise 21. ▶ [**] [HM27] Continuing the previous exercises, suppose $V_1 \ne 0$ and let $W(z) = V^{\langle -1\rangle}(z)$. The purpose of this exercise is to show that the power matrices of $V$ and $W$ are "dual" to each other; for example, when $V(z) = \ln(1/(1-z))$ we have $V^{\langle -1\rangle}(z) = 1 - e^{-z}$, $W(z) = e^z - 1$, and the corresponding power matrices are the well-known Stirling triangles $s_{nk} = \left[{n\atop k}\right]$, $w_{nk} = \left{{n\atop k}\right}$.
a) Prove that the inversion formulas 1.2.6–(47) for Stirling numbers hold in general:
$$\sum_{k} w_{nk} v_{km}(-1)^{n-k} = \sum_{k} w_{nk}(-1)^{n-k} = \delta_{nm}.$$
b) The relation $v_{n(n-k)} = n!\left{n\atop k}\right^{n-k}$ shows that, for fixed $k$, the quantity $v_{n(n-k)}/V_1^n$ is a polynomial in $n$ of degree $\le 2k$. We can therefore define
$$v_{n(n-k)} = n!\left{n\atop k}\right^{n-k}$$
for arbitrary $n$ when $k$ is a nonnegative integer, as we did for Stirling numbers in Section 1.2.6. Prove that $v_{\langle -k\rangle,-k\rangle} = w_{nk}$. (This generalizes Eq. 1.2.6–(58).)
Verified: no
Solve time: 2m17s
Correctness
The proposed solution does not correctly prove the stated matrix-product formula.
The power matrix is defined by
$$ V(z)^n=n\sum_{k\ge0}v_{nk}z^k,\qquad U(z)^n=n\sum_{k\ge0}u_{nk}z^k,\qquad W(z)^n=n\sum_{k\ge0}w_{nk}z^k. $$
Starting from
$$ W(z)=U(V(z)), $$
one should write
$$ W(z)^n=(U(V(z)))^n=U(V(z))^n. $$
Then, using the defining expansion for the $n$th power of $U$,
$$ U(t)^n=n\sum_{j\ge0}u_{nj}t^j, $$
with $t=V(z)$,
$$ W(z)^n =n\sum_{j\ge0}u_{nj}V(z)^j. $$
Substituting
$$ V(z)^j=j\sum_{k\ge0}v_{jk}z^k $$
and comparing coefficients yields
$$ w_{nk}=\sum_{j\ge0}u_{nj}v_{jk}. $$
This corresponds to the matrix product of the power matrix of $U$ with the power matrix of $V$.
The exercise, however, asks for the power matrix of $W$ to be the product of the power matrices of $V$ and $U$, namely
$$ w_{nk}=\sum_j v_{nj}u_{jk}. $$
To obtain that formula one must use the convention that power matrices act on the right. The proposed solution neither derives the stated formula nor explains the indexing convention needed to reconcile the two expressions.
Gaps and Errors
The step
$$ W(z)^n =n\sum_{m\ge0}\Bigl(\sum_{k\ge0}u_{nk}v_{km}\Bigr)z^m $$
correctly leads to
$$ w_{nm}=\sum_{k\ge0}u_{nk}v_{km}. $$
But the solution then states:
Renaming indices gives the stated matrix-product formula,
$$ w_{nk}=\sum_j v_{nj}u_{jk}. $$
This is a Critical error. Renaming dummy indices cannot interchange the roles of the free indices and reverse the order of multiplication. The formula
$$ \sum_k u_{nk}v_{km} $$
is not the same as
$$ \sum_j v_{nj}u_{jm}. $$
The solution therefore proves a different identity from the one requested.
The final sentence claims that the result shows the power matrix of $W$ is the product of the power matrices of $V$ and $U$. This conclusion is unsupported because the computation actually yields the opposite order.
Summary
The derivation up to coefficient comparison is algebraically correct, but it produces
$$ w_{nk}=\sum_j u_{nj}v_{jk}, $$
not the required formula
$$ w_{nk}=\sum_j v_{nj}u_{jk}. $$
The passage from one expression to the other is invalid. The solution therefore does not establish the theorem as stated.
VERDICT: FAIL, the computation yields $w_{nk}=\sum_j u_{nj}v_{jk}$, and the claimed conversion to $w_{nk}=\sum_j v_{nj}u_{jk}$ is invalid.