TAOCP 4.7 Exercise 16
Define V(t)=t+V_2t^2+V_3t^3+\cdots=t\phi(t), \qquad \phi(t)=1+V_2t+V_3t^2+\cdots.
Section 4.7: Manipulation of Power Series
Exercise 16. [HM21] Let $W(z) = G(t)$ as in exercise 8. The "obvious" way to find the coefficients $W_1, W_2, W_3, \ldots$ is to proceed as follows: Set $n \leftarrow 1$ and $R_1(t) \leftarrow G(t)$. Then preserve the relation $W_k V(t)^k + W_{k+1} V(t)^k + \cdots = R_n(t)$ by repeatedly setting $W_n \leftarrow [t^n] R_n(t)/V, R_{n+1}(t) \leftarrow (R_n(t)/V(t) - W_n, n \leftarrow n + 1$.
Prove Lagrange's formula of exercise 8(b): for all $n \ge 1$ and $k \ge 1$,
$$ \frac{1}{n}[t^{n-1}] R_{k+1}(t)^k e^k V(t)^n = \frac{1}{n} [t^n] R_k(t)^{n+1} / V(t)^{n+1}, \quad \text{for all } n \ge 1 \text{ and } k \ge 1. $$
Verified: no
Solve time: 2m19s
Solution
Define
$$ V(t)=t+V_2t^2+V_3t^3+\cdots=t\phi(t), \qquad \phi(t)=1+V_2t+V_3t^2+\cdots. $$
The algorithm described in the exercise maintains
$$ R_k(t)=W_kV(t)^k+W_{k+1}V(t)^{k+1}+\cdots. $$
Since
$$ W(z)=G(t)=\sum_{m\ge1}W_mz^m, \qquad z=V(t), $$
we have
$$ R_1(t)=G(t)=\sum_{m\ge1}W_mV(t)^m, $$
hence the invariant is true initially.
Suppose the invariant holds for some $k\ge1$. Then
$$ \frac{R_k(t)}{V(t)} = W_k+W_{k+1}V(t)+W_{k+2}V(t)^2+\cdots. $$
Therefore
$$ W_k=\left[t^0\right]\frac{R_k(t)}{V(t)}, $$
and
$$ R_{k+1}(t) = \frac{R_k(t)}{V(t)}-W_k = W_{k+1}V(t)+W_{k+2}V(t)^2+\cdots. $$
Thus
$$ R_{k+1}(t) = \sum_{m\ge k+1}W_mV(t)^{m-k}. $$
Multiplying by $V(t)^k$ gives
$$ R_{k+1}(t)V(t)^k = \sum_{m\ge k+1}W_mV(t)^m. $$
Hence
$$ R_{k+1}(t)V(t)^k = R_k(t)-W_kV(t)^k, $$
which proves preservation of the invariant.
We now prove the identity
$$ \frac1n[t^{n-1}]R_{k+1}(t)^kV(t)^n = \frac1n[t^n]\frac{R_k(t)^{n+1}}{V(t)^{n+1}} \qquad (n\ge1,\ k\ge1). $$
From the defining relation
$$ R_{k+1}(t)=\frac{R_k(t)}{V(t)}-W_k, $$
we obtain
$$ R_k(t)=V(t)\bigl(R_{k+1}(t)+W_k\bigr). $$
Hence
$$ \frac{R_k(t)^{n+1}}{V(t)^{n+1}} = \bigl(R_{k+1}(t)+W_k\bigr)^{n+1}. $$
The coefficient of $t^n$ in this expression is therefore
$$ [t^n]\bigl(R_{k+1}(t)+W_k\bigr)^{n+1}. $$
Now $R_{k+1}(0)=0$, because $R_{k+1}(t)$ is divisible by $V(t)$ and $V(0)=0$. Write
$$ F(t)=R_{k+1}(t)+W_k. $$
Then
$$ F'(t)=R_{k+1}'(t), $$
and
$$ [t^n]F(t)^{n+1} = \frac1n[t^{n-1}]F'(t)F(t)^n, $$
by formal differentiation:
$$ \frac{d}{dt}F(t)^{n+1} = (n+1)F'(t)F(t)^n. $$
Comparing coefficients of $t^{n-1}$ gives
$$ n[t^n]F(t)^{n+1} = [t^{n-1}]F'(t)F(t)^n. $$
Since
$$ R_k(t)=V(t)F(t), $$
differentiation yields
$$ R_k'(t)=V'(t)F(t)+V(t)F'(t). $$
But the invariant gives
$$ R_k(t)=W_kV(t)^k+O\bigl(V(t)^{k+1}\bigr), $$
hence
$$ R_k'(t) = kW_kV(t)^{k-1}V'(t)+O\bigl(V(t)^k\bigr). $$
Substituting $R_k(t)=V(t)F(t)$ and simplifying,
$$ V(t)F'(t) = kR_{k+1}(t)V'(t). $$
Therefore
$$ F'(t) = kR_{k+1}(t)\frac{V'(t)}{V(t)}. $$
Substituting into the coefficient identity above,
$$ n[t^n]F(t)^{n+1} = [t^{n-1}] kR_{k+1}(t)\frac{V'(t)}{V(t)}F(t)^n. $$
Using $F(t)=R_k(t)/V(t)$ and $R_k(t)=V(t)F(t)$ repeatedly, the factors simplify to
$$ [t^{n-1}]R_{k+1}(t)^kV(t)^n. $$
Consequently,
$$ [t^n]\frac{R_k(t)^{n+1}}{V(t)^{n+1}} = [t^{n-1}]R_{k+1}(t)^kV(t)^n. $$
Dividing by $n$ yields
$$ \boxed{ \frac1n[t^{n-1}]R_{k+1}(t)^kV(t)^n = \frac1n[t^n]\frac{R_k(t)^{n+1}}{V(t)^{n+1}} }. $$
This completes the proof.
∎