TAOCP 4.5.3 Exercise 4

Let D_n= K_n(x_1,\ldots,x_n)\,K_n(x_2,\ldots,x_{n+1}) - K_{n+1}(x_1,\ldots,x_{n+1})\,K_{n-1}(x_2,\ldots,x_n).

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 4. [M20] Prove Eq. (8).

Verified: yes
Solve time: 41m25s

Solution

Let

$$ D_n= K_n(x_1,\ldots,x_n),K_n(x_2,\ldots,x_{n+1}) - K_{n+1}(x_1,\ldots,x_{n+1}),K_{n-1}(x_2,\ldots,x_n). $$

Equation (8) asserts that

$$ D_n=(-1)^n \qquad (n\ge1). $$

We shall prove this by showing that $D_n=D_{n-2}$, then checking the two initial values.

Recall the continuant recurrence

$$ K_n(x_1,\ldots,x_n) = x_nK_{n-1}(x_1,\ldots,x_{n-1}) + K_{n-2}(x_1,\ldots,x_{n-2}), $$

valid for $n\ge2$, together with $K_0=1$ and $K_1(x)=x$.

Initial values

For $n=1$,

$$ K_2(x_1,x_2)=x_1x_2+1, $$

hence

$$ \begin{aligned} D_1 &= K_1(x_1)K_1(x_2)-K_2(x_1,x_2)K_0 \ &= x_1x_2-(x_1x_2+1) \ &=-1. \end{aligned} $$

For $n=2$,

$$ K_2(x_1,x_2)=x_1x_2+1, \qquad K_2(x_2,x_3)=x_2x_3+1, $$

and

$$ K_3(x_1,x_2,x_3) = x_3K_2(x_1,x_2)+K_1(x_1) = x_1x_2x_3+x_3+x_1. $$

Therefore

$$ \begin{aligned} D_2 &=(x_1x_2+1)(x_2x_3+1) -\bigl(x_1x_2x_3+x_3+x_1\bigr)x_2\ &=x_1x_2^2x_3+x_1x_2+x_2x_3+1 -x_1x_2^2x_3-x_2x_3-x_1x_2\ &=1. \end{aligned} $$

Thus

$$ D_1=-1,\qquad D_2=1. $$

Derivation of the recurrence $D_n=D_{n-2}$

Let $n\ge3$. Using the recurrence for the second factor of $D_n$ and for $K_{n+1}$,

$$ K_n(x_2,\ldots,x_{n+1}) = x_{n+1}K_{n-1}(x_2,\ldots,x_n) + K_{n-2}(x_2,\ldots,x_{n-1}), $$

$$ K_{n+1}(x_1,\ldots,x_{n+1}) = x_{n+1}K_n(x_1,\ldots,x_n) + K_{n-1}(x_1,\ldots,x_{n-1}), $$

we obtain

$$ \begin{aligned} D_n &= K_n(x_1,\ldots,x_n) \Bigl( x_{n+1}K_{n-1}(x_2,\ldots,x_n) + K_{n-2}(x_2,\ldots,x_{n-1}) \Bigr) \ &\quad- \Bigl( x_{n+1}K_n(x_1,\ldots,x_n) + K_{n-1}(x_1,\ldots,x_{n-1}) \Bigr) K_{n-1}(x_2,\ldots,x_n). \end{aligned} $$

The terms containing $x_{n+1}$ cancel, leaving

$$ D_n = K_n(x_1,\ldots,x_n)K_{n-2}(x_2,\ldots,x_{n-1}) - K_{n-1}(x_1,\ldots,x_{n-1})K_{n-1}(x_2,\ldots,x_n). $$

Now expand $K_n(x_1,\ldots,x_n)$ and $K_{n-1}(x_2,\ldots,x_n)$:

$$ K_n(x_1,\ldots,x_n) = x_nK_{n-1}(x_1,\ldots,x_{n-1}) + K_{n-2}(x_1,\ldots,x_{n-2}), $$

$$ K_{n-1}(x_2,\ldots,x_n) = x_nK_{n-2}(x_2,\ldots,x_{n-1}) + K_{n-3}(x_2,\ldots,x_{n-2}). $$

Substituting,

$$ \begin{aligned} D_n &= \Bigl( x_nK_{n-1}(x_1,\ldots,x_{n-1}) + K_{n-2}(x_1,\ldots,x_{n-2}) \Bigr) K_{n-2}(x_2,\ldots,x_{n-1}) \ &\quad- K_{n-1}(x_1,\ldots,x_{n-1}) \Bigl( x_nK_{n-2}(x_2,\ldots,x_{n-1}) + K_{n-3}(x_2,\ldots,x_{n-2}) \Bigr). \end{aligned} $$

Again the terms containing $x_n$ cancel, and we obtain

$$ \begin{aligned} D_n &= K_{n-2}(x_1,\ldots,x_{n-2}) K_{n-2}(x_2,\ldots,x_{n-1}) \ &\quad- K_{n-1}(x_1,\ldots,x_{n-1}) K_{n-3}(x_2,\ldots,x_{n-2}). \end{aligned} $$

But this is exactly

$$ D_{n-2}, $$

with $D_{n-2}$ evaluated on the variables $x_1,\ldots,x_{n-1}$. Hence

$$ D_n=D_{n-2}\qquad (n\ge3). $$

Completion of the proof

The recurrence $D_n=D_{n-2}$ shows that all odd-indexed values equal $D_1$, and all even-indexed values equal $D_2$:

$$ D_{2m-1}=D_1=-1, \qquad D_{2m}=D_2=1. $$

Therefore

$$ D_n= \begin{cases} -1,& n \text{ odd},\[4pt] 1,& n \text{ even}, \end{cases} $$

which is precisely

$$ D_n=(-1)^n. $$

Thus

$$ K_n(x_1,\ldots,x_n),K_n(x_2,\ldots,x_{n+1}) - K_{n+1}(x_1,\ldots,x_{n+1}),K_{n-1}(x_2,\ldots,x_n) = (-1)^n. $$

This proves Eq. (8). ∎