TAOCP 4.7 Exercise 4

Section 4.7: Manipulation of Power Series

Exercise 4. ▶ [HM23] Show that simple modifications of (9) can be used to calculate $e^{U(z)}$ when $V_0 = 0$, and $\ln V(z)$ when $V_0 = 1$.

Verified: yes
Solve time: 1m46s

Solution

Let

$W(z)=e^{U(z)}, \qquad U(z)=U_1z+U_2z^2+\cdots,$

where $U_0=0$. Then

$W'(z)=U'(z)W(z).$

Writing

$W(z)=W_0+W_1z+W_2z^2+\cdots,$

we have $W_0=e^{U_0}=1$, and

U'(z)=\sum_{k\ge1}kU_kz^{k-1}.$$ Hence $$\sum_{n\ge1}nW_nz^{n-1} = \left(\sum_{k\ge1}kU_kz^{k-1}\right) \left(\sum_{m\ge0}W_mz^m\right).$$ Equating coefficients of $z^{n-1}$ gives $$nW_n=\sum_{k=1}^n kU_kW_{n-k},$$ therefore $$W_n=\frac1n\sum_{k=1}^n kU_kW_{n-k}. \eqno(A)$$ This recurrence determines successively the coefficients of $e^{U(z)}$. Now let $$W(z)=\ln V(z), \qquad V(z)=1+V_1z+V_2z^2+\cdots,$$ where $V_0=1$. Since $$W'(z)=\frac{V'(z)}{V(z)},$$ we obtain $$W'(z)V(z)=V'(z).$$ Writing $$W(z)=W_1z+W_2z^2+\cdots,$$ because $W_0=\ln1=0$, we have $$\left(\sum_{k\ge1}kW_kz^{k-1}\right) \left(\sum_{m\ge0}V_mz^m\right) = \sum_{n\ge1}nV_nz^{n-1},

with $V_0=1$. Equating coefficients of $z^{n-1}$ yields

$\sum_{k=1}^n kW_kV_{n-k}=nV_n.$

Separating the term $k=n$ gives

$nW_nV_0+\sum_{k=1}^{n-1}kW_kV_{n-k}=nV_n.$

Since $V_0=1$,

$nW_n=nV_n-\sum_{k=1}^{n-1}kW_kV_{n-k},$

hence

= V_n-\frac1n\sum_{k=1}^{n-1}kW_kV_{n-k}. \eqno(B)$$This recurrence determines successively the coefficients of $\ln V(z)$. Formulas (A) and (B) are direct analogues of (9), obtained from differential equations satisfied by the corresponding functions. ∎