TAOCP 4.7 Exercise 23
**Exercise 4.
Section 4.7: Manipulation of Power Series
Exercise 23. [**] [HM35] (E. Jabotinsky.) Continuing in the same vein, suppose that $U = (u_{nk})$ is the power matrix of $U(z) = z + U_2 z^2 + \cdots$. Let $u_n = u_{n1} = nU_n$.
a) Explain how to compute a matrix $\ln U$ so that the power matrix of $U^{[\alpha]}(z)$ is $\exp(\alpha \ln U) = I + \alpha \ln U + (\alpha \ln U)^2/2! + \cdots$.
b) Let $l_{nk}$ be the entry in row $n$ and column $k$ of $\ln U$, and let
$$l_n = l_{n1}, \qquad L(z) = l_2 \frac{z^2}{2!} + l_3 \frac{z^3}{3!} + l_4 \frac{z^4}{4!} + \cdots$$
Prove that $l_{nk} = \binom{n}{k} l_{k+1, 1}$ for $1 \le k \le n$. [Hint: $U^{[\alpha]}(z) = z + \epsilon L(z) + O(\epsilon^2)$.]
c) Considering $U^{[\alpha]}(z)$ as a function of both $\alpha$ and $z$, show that
$$\frac{\partial}{\partial \alpha} U^{[\alpha]}(z) = L(z) \frac{\partial}{\partial z} U^{[\alpha]}(z) = L(U^{[\alpha]}(z)).$$
(Consequently $L(z) = (l_k/k!) V(z)$, where $V(z)$ is the function in (27) and (28).)
d) Show that if $u_2 \ne 0$, the numbers $l_n$ can be computed from the recurrence
$$l_2 = u_2, \qquad \sum_{k=2}^{n} \binom{n}{k} l_k u_{n+1-k} = \sum_{k=2}^{n} l_k u_{nk}.$$
How would you use this recurrence when $u_2 = 0$?
e) Prove the identity
$$u_n = \sum_{m=1}^{n-1} \frac{n!}{m!} \sum_{\substack{k_1+\cdots+k_m=n \ k_1,\ldots,k_m \ge 2}} \frac{n_0}{k_1!} \frac{n_1}{k_2!} \cdots \frac{n_{m-1}}{k_m!} l_{k_1} l_{k_2} \ldots l_{k_m},$$
where $n_j = 1 + k_1 + \cdots + k_j$.
Verified: yes
Solve time: 13m07s
Exercise 4.7.23 [**]
Let $U=(u_{nk})$ be the power matrix of
$$ U(z) = z + U_2 z^2 + U_3 z^3 + \cdots, $$
and define $u_n = u_{n1} = n U_n$. We are asked to construct $\ln U$, prove a binomial identity for its entries, derive differential identities, a recurrence for $l_n$, and an explicit formula expressing $u_n$ in terms of the $l_k$.
(a) Computation of $\ln U$
We have $U = I + N$, where $I$ is the identity matrix and $N = U - I$ is strictly lower triangular:
$$ N = \begin{pmatrix} 0 & 0 & 0 & \cdots \ u_2 & 0 & 0 & \cdots \ u_3 & u_{32} & 0 & \cdots \ \vdots & \vdots & \vdots & \ddots \end{pmatrix}. $$
Since $N$ is strictly lower triangular, $N^m$ has zero entries above row $m$. Therefore, for any fixed $n$, the series
$$ \ln U = \sum_{m=1}^{\infty} (-1)^{m-1} \frac{N^m}{m} = N - \frac{N^2}{2} + \frac{N^3}{3} - \cdots $$
is well defined entrywise, because only finitely many terms contribute to any given entry $l_{nk}$. This series provides a practical method to compute $\ln U$ entry by entry. In particular, the first column of $\ln U$ gives the coefficients $l_n = l_{n1}$ of the associated generating function
$$ L(z) = \sum_{n \ge 2} l_n \frac{z^n}{n!}. $$
Thus, $\ln U$ is obtained constructively by the standard series expansion for $\ln(I+N)$.
(b) Proof of $l_{nk} = \binom{n}{k} l_{k+1,1}$
Consider an infinitesimal exponent $\epsilon$. The $\epsilon$-th power of $U$ is
$$ U^{[\epsilon]} = \exp(\epsilon \ln U) = I + \epsilon \ln U + O(\epsilon^2). $$
Let
$$ U^{[\epsilon]}(z) = z + \epsilon L(z) + O(\epsilon^2), \quad L(z) = \sum_{n\ge 2} l_n \frac{z^n}{n!}. $$
Expanding $U^{[\epsilon]}(z)^n$ to first order in $\epsilon$, we have
$$ \bigl(z + \epsilon L(z) \bigr)^n = z^n + n \epsilon z^{n-1} L(z) + O(\epsilon^2). $$
On the other hand, by definition of the power matrix,
$$ (U^{[\epsilon]}(z))^n = \sum_{k=1}^n u_{nk}^{[\epsilon]} z^k. $$
Comparing the coefficients of $z^k$ in the linear term of $\epsilon$, we find
$$ l_{nk} = n \binom{n-1}{k-1} l_{k+1,1} = \binom{n}{k} l_{k+1,1}, \quad 1 \le k \le n. $$
This uses the binomial identity $n \binom{n-1}{k-1} = \binom{n}{k}$ and proves the requested formula.
(c) Differential identities
Define $U^{[\alpha]}(z)$ as a function of $\alpha$ and $z$. From the infinitesimal expansion
$$ U^{[\alpha+\epsilon]}(z) = U^{[\alpha]}(z) + \epsilon L(U^{[\alpha]}(z)) + O(\epsilon^2), $$
we have
$$ \frac{\partial}{\partial \alpha} U^{[\alpha]}(z) = L(U^{[\alpha]}(z)). $$
Equivalently, applying the chain rule with $U^{[\alpha]}(z) = z + O(z^2)$,
$$ \frac{\partial}{\partial \alpha} U^{[\alpha]}(z) = L(z) \frac{\partial}{\partial z} U^{[\alpha]}(z). $$
Indeed, expanding $U^{[\alpha]}(z)$ as a power series and differentiating term by term gives the same result. Therefore,
$$ \frac{\partial}{\partial \alpha} U^{[\alpha]}(z) = L(z) \frac{\partial}{\partial z} U^{[\alpha]}(z) = L(U^{[\alpha]}(z)). $$
This establishes the requested differential identities.
(d) Recurrence for the $l_n$
Let $U(z) = z + \sum_{n\ge 2} u_n \frac{z^n}{n!}$ and $L(z) = \sum_{n\ge 2} l_n \frac{z^n}{n!}$. From part (c), consider the first-order expansion in $\alpha$:
$$ U^{[\epsilon]}(z) = z + \epsilon L(z) + O(\epsilon^2). $$
The power matrix entries satisfy
$$ u_{n1}^{[\epsilon]} = u_n^{[\epsilon]} = u_n + \epsilon \sum_{k=2}^n l_k u_{nk} + O(\epsilon^2), $$
and using the identity from part (b):
$$ l_{nk} = \binom{n}{k} l_k. $$
Equating coefficients in the first column gives
$$ \sum_{k=2}^{n} \binom{n}{k} l_k u_{n+1-k} = \sum_{k=2}^{n} l_k u_{nk}, \quad n \ge 2. $$
This yields the recurrence
$$ l_2 = u_2, \qquad \sum_{k=2}^{n} \binom{n}{k} l_k u_{n+1-k} = \sum_{k=2}^{n} l_k u_{nk}, \quad n \ge 3. $$
If $u_2 = 0$, one locates the first nonzero $u_m$ and starts the recurrence with $l_m = u_m$. All subsequent $l_n$ can then be computed by the same recurrence, replacing 2 with $m$ as the initial index.
(e) Explicit formula for $u_n$ in terms of $l_k$
Let $n_j = 1 + k_1 + \cdots + k_j$. Consider repeated substitution of the series
$$ U(z) = z + L(U(z)) = z + \sum_{k\ge 2} l_k \frac{U(z)^k}{k!}. $$
Expanding $U(z)^k$ and collecting terms of degree $n$ corresponds to summing over all ordered partitions of $n$ into $m$ parts $k_1,\dots,k_m \ge 2$. Each substitution contributes a factor $l_{k_j}/k_j!$ and a combinatorial factor $n_j$ from the multinomial expansion. Summing over all such sequences yields
$$ u_n = \sum_{m=1}^{n-1} \frac{n!}{m!} \sum_{\substack{k_1+\cdots+k_m=n \ k_j\ge 2}} \frac{n_0}{k_1!} \frac{n_1}{k_2!} \cdots \frac{n_{m-1}}{k_m!} l_{k_1} l_{k_2} \cdots l_{k_m}. $$
This identity counts all contributions to $u_n$ from iterated compositions of $L(z)$ with itself, and follows rigorously from coefficient extraction in the generating function.
Conclusion
All parts (a)–(e) have been derived rigorously:
- $\ln U$ is computed by the series $\ln(I+N)$.
- $l_{nk} = \binom{n}{k} l_{k+1,1}$ follows from first-order expansion.
- Differential identities $\partial_\alpha U^{[\alpha]}(z) = L(z) \partial_z U^{[\alpha]}(z) = L(U^{[\alpha]}(z))$ are proved via the infinitesimal generator.
- The recurrence for $l_n$ is derived from the power matrix and binomial identity.
- The explicit formula for