TAOCP 4.7 Exercise 2

Let $U(z) = U_0 + U_1 z + U_2 z^2 + \cdots, \qquad V(z) = V_0 + V_1 z + V_2 z^2 + \cdots$ be power series with integer coefficients, and suppose $V_0 \ne 0$.

taocpmathematicsalgorithmsvolume-2medium

Section 4.7: Manipulation of Power Series

Exercise 2. [20] If the coefficients of $U(z)$ and $V(z)$ are integers and $V_0 \ne 0$, find a recurrence relation for the integers $V_0^{n+1}W_n$, where $W_n$ is defined by (3). How could you use this for power series division?

Verified: yes
Solve time: 2m41s

Solution

Let

$U(z) = U_0 + U_1 z + U_2 z^2 + \cdots, \qquad V(z) = V_0 + V_1 z + V_2 z^2 + \cdots$

be power series with integer coefficients, and suppose $V_0 \ne 0$. Let $W(z) = U(z)/V(z)$, with

$W(z) = W_0 + W_1 z + W_2 z^2 + \cdots.$

By equation (2) of Section 4.7, the coefficients $W_n$ satisfy

$W_n = \frac{1}{V_0} \left(U_n - \sum_{j=1}^{n} V_j W_{n-j} \right), \quad n \ge 0.$

Since $U_n$ and $V_j$ are integers, the $W_n$ may not be integers. To obtain an all-integer recurrence, we multiply both sides of this equation by $V_0^{n+1}$. Define

$X_n := V_0^{n+1} W_n.$

Then, for $n = 0$, we have

$X_0 = V_0 W_0 = V_0 \cdot \frac{U_0}{V_0} = U_0,$

which is an integer. For $n \ge 1$, multiply equation (2) by $V_0^{n+1}$:

\begin{align*}

V_0^{n+1} W_n &= V_0^{n+1} \cdot \frac{1}{V_0} \left(U_n - \sum_{j=1}^{n} V_j W_{n-j} \right) \

&= V_0^n U_n - V_0^n \sum_{j=1}^{n} V_j W_{n-j} \

&= V_0^n U_n - \sum_{j=1}^{n} V_j V_0^n W_{n-j} \

&= V_0^n U_n - \sum_{j=1}^{n} V_j V_0^n \cdot V_0^{-(n-j+1)} X_{n-j} \

&= V_0^n U_n - \sum_{j=1}^{n} V_j V_0^{j-1} X_{n-j}.

\end{align*}

Thus the integers $X_n$ satisfy the recurrence

$\boxed{X_0 = U_0, \qquad X_n = V_0^n U_n - \sum_{j=1}^{n} V_j V_0^{j-1} X_{n-j}, \quad n \ge 1.} \eqno(*)$

This is a recurrence purely in integers: each $X_n$ is an integer linear combination of previous $X_{n-j}$ and $V_0^n U_n$. It can be computed successively for $n = 0,1,2,\ldots$, yielding the integer sequence $X_n = V_0^{n+1} W_n$.

To perform power series division with integers using this recurrence, one proceeds as follows. Input the integer coefficients $U_n$ and $V_n$ and compute $X_0 = U_0$. For each $n \ge 1$, compute $X_n$ using $(*)$, then recover $W_n$ as

$W_n = \frac{X_n}{V_0^{n+1}}.$

This allows exact computation of the rational coefficients $W_n$ without performing fractional arithmetic until the final division by $V_0^{n+1}$.

This completes the proof.

∎