TAOCP 4.7 Exercise 1
If $V_0 = 0$, let $m$ be the smallest index such that $V_m \ne 0$.
Section 4.7: Manipulation of Power Series
Exercise 1. [M10] The text explains how to divide $U(z)$ by $V(z)$ when $V_0 \ne 0$; how should the division be done when $V_0 = 0$?
Verified: yes
Solve time: 1m53s
If $V_0 = 0$, let $m$ be the smallest index such that $V_m \ne 0$. Then we can factor $z^m$ from $V(z)$ and write
$V(z) = z^m \bigl(V_m + V_{m+1} z + V_{m+2} z^2 + \cdots\bigr).$
The division problem $W(z) = U(z)/V(z)$ can then be reduced to dividing the shifted series $z^{-m}U(z)$ by the series $V_m + V_{m+1} z + V_{m+2} z^2 + \cdots$, which has a nonzero constant term. Specifically, we define
$\widetilde{U}(z) \leftarrow z^{-m} U(z), \qquad \widetilde{V}(z) \leftarrow V_m + V_{m+1} z + V_{m+2} z^2 + \cdots,$
compute $\widetilde{W}(z) = \widetilde{U}(z)/\widetilde{V}(z)$ using the recurrence (2), and then recover
$W(z) = z^{-m} \widetilde{W}(z).$
This requires exactly one factorization and one application of the standard division algorithm for a series with nonzero constant term. This completes the solution. ∎