TAOCP 4.6.4 Exercise 37

Section 4.6.4: Evaluation of Polynomials

Exercise 37. [M21] (T. S. Motzkin.) Show that "almost all" rational functions of the form

$$( a_n x^n + a_{n-1} x^{n-1} + \cdots + u_1 x + a_0 ) / (x^n + b_{n-1} x^{n-1} + \cdots + c_1 x + c_0),$$

with coefficients in a field $S$, can be evaluated using the expansion

$$\alpha_1 + \beta_1/(x + \alpha_2 + \beta_2/(x + \cdots + \beta_n/(x + \alpha_{n+1})\cdots)),$$

for suitable $\alpha_j$, $\beta_j$ in $S$. (This continued fraction scheme has $n$ divisions and $2n$ additions; by "almost all" rational functions we mean all except those whose coefficients satisfy some nontrivial polynomial equation.) Determine the $\alpha$'s and $\beta$'s for the rational function $(x^2 + 10x + 29)/(x^2 + 8x + 19)$.

Verified: yes
Solve time: 4m56s

Solution

Let

$$ R(x)=\frac{P_0(x)}{Q_0(x)} =\frac{a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0} {x^n+b_{n-1}x^{,n-1}+\cdots+b_0}, $$

where $Q_0$ is monic of degree $n$.

We shall show that, for generic coefficients, $R(x)$ admits a continued fraction expansion

$$ R(x) = \alpha_1+\frac{\beta_1} {x+\alpha_2+\frac{\beta_2} {x+\alpha_3+\cdots+\frac{\beta_n}{x+\alpha_{n+1}}}}. $$

The construction is the Euclidean algorithm applied in a normalized form.

Define recursively rational functions

$$ R_k(x)=\frac{P_k(x)}{Q_k(x)}, $$

with $Q_k$ monic and $\deg P_k=\deg Q_k=m$. Since the numerator and denominator have the same degree, there is a unique $\alpha_{k+1}\in S$ such that

$$ P_k(x)-\alpha_{k+1}Q_k(x) $$

has degree $<m$. Write

$$ P_k(x)-\alpha_{k+1}Q_k(x)=\beta_{k+1}Q_{k+1}(x), $$

where $Q_{k+1}$ is monic. For generic coefficients, the leading coefficient

$\beta_{k+1}$ is nonzero. Then

$$ R_k(x) = \alpha_{k+1} +\beta_{k+1}\frac{Q_{k+1}(x)}{Q_k(x)}. $$

Since $Q_k$ is monic of degree $m$ and $Q_{k+1}$ is monic of degree

$m-1$, polynomial division gives

$$ Q_k(x)=(x+\gamma_{k+2})Q_{k+1}(x)+(\text{polynomial of degree}<m-1). $$

Because $Q_{k+1}$ is monic, the quotient is exactly $x+\gamma_{k+2}$.

Hence

$$ \frac{Q_k(x)}{Q_{k+1}(x)} = x+\gamma_{k+2} +\frac{\text{lower-degree polynomial}}{Q_{k+1}(x)}. $$

Taking reciprocals yields another rational function of the same type but with

degree reduced by $1$. Repeating the process decreases the degree at each

step and therefore terminates after $n$ stages.

The only obstruction occurs when some $\beta_j=0$. Each $\beta_j$ is a

polynomial expression in the original coefficients. Thus failure occurs only on

the algebraic set defined by

$$ \beta_1\beta_2\cdots\beta_n=0. $$

This is a nontrivial polynomial equation in the coefficients. Therefore all

rational functions except those lying on this proper algebraic subset admit the

desired continued fraction expansion. This is the meaning of “almost all”.

Now consider

$$ R(x)=\frac{x^2+10x+29}{x^2+8x+19}. $$

Let

$$ P_0(x)=x^2+10x+29,\qquad Q_0(x)=x^2+8x+19. $$

Since the leading coefficients are equal,

$$ \alpha_1=1. $$

Indeed,

$$ P_0-Q_0=2x+10=2(x+5), $$

$$ R(x) = 1+2,\frac{x+5}{x^2+8x+19}. $$

Hence

$$ \beta_1=2, \qquad Q_1(x)=x+5. $$

Next divide $Q_0$ by $Q_1$:

$$ x^2+8x+19=(x+3)(x+5)+4. $$

Therefore

$$ \frac{Q_0}{Q_1} = x+3+\frac4{x+5}. $$

The quotient is already of the required form $x+\alpha_2$, so

$$ \alpha_2=3. $$

Also,

$$ 4=(4)\cdot 1, $$

hence

$$ \beta_2=4, \qquad Q_2(x)=1. $$

Finally,

$$ \frac{Q_1}{Q_2}=x+5, $$

$$ \alpha_3=5. $$

Thus

$$ R(x) = 1+\frac{2} {x+3+\frac{4}{x+5}}. $$

Hence

$$ \boxed{\alpha_1=1,\quad \beta_1=2,\quad \alpha_2=3,\quad \beta_2=4,\quad \alpha_3=5.} $$

A direct verification is straightforward:

$$ 1+\frac{2}{x+3+\frac4{x+5}} = 1+\frac{2(x+5)}{(x+3)(x+5)+4} = 1+\frac{2(x+5)}{x^2+8x+19} $$

$$= \frac{x^2+8x+19+2x+10}{x^2+8x+19} = \frac{x^2+10x+29}{x^2+8x+19}.$$

Therefore the continued fraction expansion is

$$ \boxed{ \frac{x^2+10x+29}{x^2+8x+19} = 1+\frac{2}{x+3+\frac4{x+5}} }. $$

$\square$