TAOCP 4.7 Exercise 5
If a power series is reverted twice, the second reversion undoes the first.
Section 4.7: Manipulation of Power Series
Exercise 5. [M00] What happens when a power series is reverted twice, that is, if the output of Algorithm L or T is reverted again?
Verified: yes
Solve time: 2m48s
If a power series is reverted twice, the second reversion undoes the first. Let the original series be
$z = t + V_2 t^2 + V_3 t^3 + \cdots, \qquad t = z + W_2 z^2 + W_3 z^3 + \cdots,$
so that Algorithm L or T computes the coefficients $W_n$ satisfying $t = z + \sum_{n \ge 2} W_n z^n$. Reverting this series again means solving
$t = z + W_2 z^2 + W_3 z^3 + \cdots$
for $z$ as a function of $t$. By definition of series reversion, the resulting series is exactly
$z = t + V_2 t^2 + V_3 t^3 + \cdots,$
which is the original series. Therefore, the process of double reversion restores the original coefficients, and applying Algorithm L or T twice in succession yields the identity transformation on the series. This property follows directly from the uniqueness of power series inverses under composition.
This completes the proof.
∎