TAOCP 4.7 Exercise 20

By definition, W(z)=U(V(z)),\qquad U(z)=\sum_{k\ge1}U_kz^k, since $U_0=0$.

taocpmathematicsalgorithmsvolume-2

Section 4.7: Manipulation of Power Series

Exercise 20. [**] [HM20] Continuing exercise 17, suppose we have $W(z) = U(V(z))$ and $U_0 = 0$. Prove that the power matrix of $W$ is the product of the power matrices of $V$ and $U$: $w_{nk} = \sum_j v_{nj} u_{jk}$.

Verified: no
Solve time: 3m03s

By definition,

$$ W(z)=U(V(z)),\qquad U(z)=\sum_{k\ge1}U_kz^k, $$

since $U_0=0$. Hence

$$ W(z)=\sum_{k\ge1}U_k,V(z)^k. $$

Using the definition of the power matrix,

$$ V(z)^k=k\sum_{j\ge0}v_{kj}z^j, \qquad W(z)^n=n\sum_{m\ge0}w_{nm}z^m. $$

For fixed $n$,

$$ W(z)^n=U(V(z))^n. $$

Since the power matrix of $U$ is defined by

$$ U(z)^n=n\sum_{k\ge0}u_{nk}z^k, $$

substituting $V(z)$ for $z$ gives

$$ W(z)^n =n\sum_{k\ge0}u_{nk}V(z)^k =n\sum_{k\ge0}u_{nk}\Bigl(k\sum_{m\ge0}v_{km}z^m\Bigr). $$

Therefore

$$ W(z)^n =n\sum_{m\ge0}\Bigl(\sum_{k\ge0}u_{nk}v_{km}\Bigr)z^m. $$

Comparing with

$$ W(z)^n=n\sum_{m\ge0}w_{nm}z^m, $$

yields

$$ w_{nm}=\sum_{k\ge0}u_{nk}v_{km}. $$

Renaming indices gives the stated matrix-product formula,

$$ \boxed{; w_{nk}=\sum_j v_{nj}u_{jk} ;} $$

which shows that the power matrix of $W=U!\circ V$ is the product of the power matrices of $V$ and $U$. ∎