TAOCP 4.7 Exercise 8
Let z=V(t)=V_1t+V_2t^2+V_3t^3+\cdots,\qquad V_1\neq0, and let
Section 4.7: Manipulation of Power Series
Exercise 8. ▶ [M25] If $W(z) = W_1 z + W_2 z^2 + W_3 z^3 + \cdots = G_1 t + G_2 t^2 + G_3 t^3 + \cdots = G(t)$, where $z = V_1 t + V_2 t^2 + V_3 t^3 + \cdots$ and $V_1 \ne 0$, Lagrange proved that
$$W_n = \frac{1}{n} [t^{n-1}], G'(t) / (V_1 + V_2 t + V_3 t^2 + \cdots)^n.$$
(Equation (12) is the special case $G_1 = V_1 = 1$, $G_2 = G_3 = \cdots = 0$.) Extend Algorithm L so that it obtains the coefficients $W_1, W_2, \ldots$ in more general situation, without substantially increasing its running time.
Verified: yes
Solve time: 19m12s
Solution
Let
$$ z=V(t)=V_1t+V_2t^2+V_3t^3+\cdots,\qquad V_1\neq0, $$
and let
$$ W(z)=\sum_{n\ge1}W_nz^n=G(t)=\sum_{m\ge1}G_mt^m . $$
Lagrange's formula gives
$$ W_n=\frac1n[t^{,n-1}] \frac{G'(t)} {(V_1+V_2t+V_3t^2+\cdots)^n}. \tag{1} $$
The problem is to modify Algorithm L so that it computes these coefficients with essentially the same cost as in the special case $G(t)=t$.
1. The quantities maintained by Algorithm L
Write
$$ A(t)=V_1+V_2t+V_3t^2+\cdots . $$
Algorithm L is based on the coefficients
$$ A(t)^{-n} =U_0^{(n)}+U_1^{(n)}t+\cdots+U_{n-1}^{(n)}t^{,n-1} +O(t^n). \tag{2} $$
The recurrence of Algorithm L updates these coefficients from stage
$n-1$ to stage $n$. Nothing in that recurrence depends on the special choice $G(t)=t$; it depends only on $A(t)$.
Therefore the original Algorithm L may be run unchanged. At stage $n$ it supplies the coefficients
$$ U_0^{(n)},U_1^{(n)},\ldots,U_{n-1}^{(n)} $$
of $A(t)^{-n}$ through degree $n-1$.
In the special case $G(t)=t$,
$$ W_n=\frac1n,U_{n-1}^{(n)}, $$
which is exactly the quantity output by Algorithm L.
2. Formula for the general case
Write
$$ G'(t)=\sum_{m\ge0}H_m t^m, \qquad H_m=(m+1)G_{m+1}. $$
Multiplying $G'(t)$ by (2), the coefficient of $t^{n-1}$ is
$$ [t^{n-1}],G'(t)A(t)^{-n} = \sum_{k=0}^{n-1} H_k,U_{n-1-k}^{(n)}. $$
Hence (1) becomes
$$ W_n = \frac1n \sum_{k=0}^{n-1} H_k,U_{n-1-k}^{(n)} = \frac1n \sum_{k=0}^{n-1} (k+1)G_{k+1}, U_{n-1-k}^{(n)}. \tag{3} $$
Equation (3) is the only change required. The coefficients
$U_j^{(n)}$ are exactly those already produced by Algorithm L.
3. Extension of Algorithm L
Run Algorithm L exactly as in the text. In addition, store
$$ H_k=(k+1)G_{k+1} \qquad (k\ge0). $$
When stage $n$ has finished, Algorithm L has computed
$$ U_0^{(n)},U_1^{(n)},\ldots,U_{n-1}^{(n)}. $$
Replace the original output step by
$$ S_n \leftarrow \sum_{k=0}^{n-1} H_k,U_{n-1-k}^{(n)}, $$
$$ W_n\leftarrow \frac{S_n}{n}. $$
Output $W_n$.
By (3), this value is exactly the coefficient required by Lagrange's formula.
4. Running time
The original Algorithm L performs $O(n)$ arithmetic operations at stage $n$, hence $O(N^2)$ operations to obtain $W_1,\ldots,W_N$.
The modification adds only the convolution
$$ S_n=\sum_{k=0}^{n-1}H_k,U_{n-1-k}^{(n)}, $$
which requires $n$ multiplications and $n-1$ additions at stage $n$.
Therefore the additional work is
$$ \sum_{n=1}^{N} O(n)=O(N^2), $$
the same order as the original algorithm. The running time is increased only by a constant factor.
Thus Algorithm L extends to the general Lagrange inversion formula by leaving its recurrence unchanged and replacing the final output $U_{n-1}^{(n)}/n$ by the convolution formula
$$ \boxed{ W_n= \frac1n \sum_{k=0}^{n-1} (k+1)G_{k+1}, U_{n-1-k}^{(n)} }. $$
When $G(t)=t$, we have $H_0=1$ and $H_k=0$ for $k>0$, so the formula reduces to the original Algorithm L output
$$ W_n=\frac1n U_{n-1}^{(n)}. $$
This is precisely the desired extension. ∎