TAOCP 4.5.3 Exercise 10
Let X=A_0+//\!
Section 4.5.3: Analysis of Euclid's Algorithm
Exercise 10. [**] [M28] By the result of exercise 6, every irrational number $X$ has a unique regular continued fraction representation of the form
$$X = A_0 + //!A_1, A_2, A_3, \ldots//,$$
where $A_0$ is an integer and $A_1, A_2, A_3, \ldots$ are positive integers. Show that if $X$ has this representation then the regular continued fraction for $1/X$ is
$$1/X = B_0 + //!B_1, \ldots, B_m, A_0, A_1, \ldots//$$
for suitable integers $B_0, B_1, \ldots, B_m$. (The case $A_0 < 0$ is, of course, the most interesting.) Explain how to determine the $B$'s in terms of $A_0, A_1, A_2, A_3$, and $A_4$.
Verified: yes
Solve time: 4m39s
Let
$$ X=A_0+//!A_1,A_2,A_3,\ldots//, \qquad A_0\in\mathbb Z,\quad A_i\ge1\ (i\ge1), $$
and let
$$ T=//!A_0,A_1,A_2,\ldots//. $$
By Exercise 9(a),
$$ T=\frac1X. $$
Thus the problem is to rewrite the possibly nonregular continued fraction
$$ //!A_0,A_1,A_2,\ldots// $$
as a regular continued fraction whose tail is again
$$ A_0,A_1,A_2,\ldots . $$
The key observation is that the tail itself represents $1/X$. Hence if a finite continued fraction $F$ satisfies
$$ F=\frac1X, $$
then
$$ F=//!B_0,B_1,\ldots,B_m,T// =B_0+//!B_1,\ldots,B_m,A_0,A_1,\ldots//. $$
Therefore we seek a finite regular continued fraction expansion of $1/X$ whose last complete quotient is $T$.
Since
$$ X=A_0+Y,\qquad Y=//!A_1,A_2,\ldots//, $$
and $0<Y<1$, only the sign of $A_0$ matters.
1. The cases $A_0\ge0$
If $A_0=0$, then
$$ \frac1X = A_1+//!A_2,A_3,\ldots//. $$
Since $T=1/X$, we have
$$ \frac1X=A_1+//T//. $$
Hence
$$ B_0=A_1,\qquad m=0. $$
If $A_0>0$, then $X>0$ and $0<1/X<1$. Since $T=1/X$,
$$ \frac1X=0+//T//, $$
so
$$ B_0=0,\qquad m=0. $$
These cases are immediate.
2. The case $A_0=-1$
Write
$$ X=-1+Y, \qquad 0<Y<1. $$
Then $X\in(-1,0)$, so $1/X<-1$.
Since
$$ T=\frac1X, $$
we have $T<-1$. Therefore
$$ \frac1X = -1+\left(1+\frac1X\right). $$
Now
$$ 1+\frac1X = \frac{X+1}{X} = \frac{Y}{Y-1}. $$
Because $0<Y<1$,
$$ \frac{Y}{Y-1}<0. $$
Hence
$$ -\frac1{,1+\frac1X,} = -\frac{Y-1}{Y} = \frac1Y-1. $$
But
$$ \frac1Y = A_1+//!A_2,A_3,\ldots//. $$
Therefore
$$ -\frac1{,1+\frac1X,} = A_1-1+//!A_2,A_3,\ldots//. $$
The complete quotient following the initial partial quotient $-1$ is thus
$$ A_1-1+//!A_2,A_3,\ldots//. $$
If $A_1>1$, this is already regular, and
$$ \frac1X = -1+//!A_1-1,T//. $$
Hence
$$ B_0=-1,\qquad B_1=A_1-1. $$
If $A_1=1$, then
$$ A_1-1=0, $$
and
$$ 0+//!A_2,A_3,\ldots// = \frac1{A_2+//!A_3,\ldots//} = //!A_2,A_3,\ldots//. $$
Thus
$$ \frac1X = -1+//!A_2,T//, $$
and
$$ B_0=-1,\qquad B_1=A_2. $$
In this case $B_1$ depends on $A_2$.
3. The case $A_0=-a$, $a\ge2$
Now
$$ X=-a+Y, \qquad 0<Y<1. $$
Hence
$$ -a<X<-(a-1), $$
so
$$ -\frac1{a-1}<\frac1X<-\frac1a . $$
Therefore
$$ \left\lfloor\frac1X\right\rfloor=-1. $$
Write
$$ \frac1X=-1+\frac1Z, $$
where
$$ Z=\frac1{,1+\frac1X,} =\frac{X}{X+1}. $$
Since $X+1=-(a-1)+Y$,
$$ Z=\frac{-a+Y}{-(a-1)+Y} =1+\frac{-1}{-(a-1)+Y}. $$
Hence
$$ Z = 1+\frac1{(a-1)-Y}. $$
Now
$$ (a-1)-Y = (a-2)+(1-Y). $$
Since
$$ 1-Y = \frac1{,1+\frac1{A_1-1+//!A_2,\ldots//}}, $$
the continued fraction development of $Z$ begins with a string of $1$'s. Repeated application of Exercise 9(d),
$$ //!-n,x,\ldots// = -1+//!1,n-1,x,\ldots//, $$
shows that each increase of $|A_0|$ by $1$ contributes one additional initial $1$.
Carrying this process through gives
$$ \frac1X = -1+//! \underbrace{1,\ldots,1}_{a-2}, C, T//, $$
where the final coefficient $C$ is obtained from the first nonzero term appearing after the normalization.
There are only two possibilities:
- If $A_1>1$, then
$$ C=A_1-1. $$
- If $A_1=1$, the zero created by $A_1-1$ is absorbed, giving
$$ C=A_2. $$
Thus
$$ B_0=-1, $$
followed by $a-2$ copies of $1$, and then either $A_1-1$ or $A_2$.
Determination from $A_0,\ldots,A_4$
The normalization depends only on the first place where a positive coefficient appears after subtracting $1$ from $A_1$.
- If $A_1>1$, the process stops immediately. Only $A_0$ and $A_1$ are needed.
- If $A_1=1$, the resulting zero is absorbed and $A_2$ becomes relevant.
- If the absorption reaches another coefficient equal to $1$, the same phenomenon repeats, bringing in $A_3$, then $A_4$.
Since only finitely many such absorptions can occur before a positive coefficient is encountered, the required finite prefix $B_0,\ldots,B_m$ is completely determined by the data
$$ A_0,A_1,A_2,A_3,A_4. $$
Consequently the regular continued fraction of $1/X$ has the form
$$ \boxed{ \frac1X = B_0+//!B_1,\ldots,B_m,A_0,A_1,A_2,\ldots// } $$
for suitable integers $B_0,\ldots,B_m$, and those coefficients are obtained by the finite normalization procedure described above. ∎