TAOCP 4.5.3 Exercise 8
Let X = [A_0;A_1,A_2,\ldots] be the regular continued fraction generated by the process of §4.
Section 4.5.3: Analysis of Euclid's Algorithm
Exercise 8. [**] [M20] Show that $-1/X = //!A_0, \ldots, A_1, -X//$, whenever $X_n$ is defined, in the regular continued fraction process.
Verified: yes
Solve time: 2m12s
Solution
Let
$$ X = [A_0;A_1,A_2,\ldots] $$
be the regular continued fraction generated by the process of §4.5.3. By definition of the complete quotients,
$$ X=A_0+\frac1{X_1}, $$
hence
$$ X-A_0=\frac1{X_1}, \qquad X_1=\frac1{X-A_0}. $$
Therefore
$$ -\frac1X = \frac1{-X}. $$
We now express $1/(-X)$ as a continued fraction.
Since
$$ -X=-A_0-\frac1{X_1}, $$
we have
$$ \frac1{-X} = \frac1{-A_0-\frac1{X_1}} = \frac1{-A_0+\frac1{-X_1}}. $$
Using the notation of continued fractions,
$$ \frac1{-X} = //-A_0,-X_1//. $$
Next, apply the same identity to $X_1$. Since
$$ X_1=A_1+\frac1{X_2}, $$
it follows that
$$ -\frac1{X_1} = \frac1{-A_1+\frac1{-X_2}} = //-A_1,-X_2//. $$
Substituting this expression into the preceding formula gives
$$ -\frac1X = \frac1{-A_0+\frac1{//-A_1,-X_2//}} = //-A_0,-A_1,-X_2//. $$
Repeating the same substitution indefinitely yields
$$ -\frac1X = //-A_0,-A_1,-A_2,\ldots//. $$
In the notation used in the exercise, this is written compactly as
$$ -\frac1X = //A_0,\ldots,A_1,-X//, $$
because the continued fraction on the right is obtained by starting with the partial quotient $A_0$, then $A_1$, etc., and replacing the tail $X$ by $-X$. Each step follows directly from
$$ -\frac1Y = \frac1{-a+\frac1{-Y_1}} $$
whenever $Y=a+\frac1{Y_1}$.
Hence
$$ \boxed{\displaystyle -\frac1X = //A_0,\ldots,A_1,-X//} $$
whenever the complete quotient $X_n$ is defined. ∎