TAOCP 4.5.3 Exercise 6

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 6. [**] [M23] Prove that the regular continued fraction expansion of a number is unique in the following sense: If $B_1, B_2, \ldots$ are positive integers, then the infinite continued fraction $//B_1, B_2, \ldots//$ is an irrational number $X$ between 0 and 1 whose regular continued fraction has $A_n = B_n$ for all $n \ge 1$; and if $B_1, \ldots, B_m$ are positive integers with $B_m > 1$, then the regular continued fraction for $X = //B_1, \ldots, B_m//$ has $A_n = B_n$ for $1 \le n \le m$.

Verified: yes
Solve time: 23m46s

---

Let

$$ X=//B_1,B_2,\ldots//. $$

Exercise 5 shows that this infinite continued fraction exists, since the partial quotients are positive integers and therefore satisfy $B_j\ge1$. Let

$$ X_n=//B_{n+1},B_{n+2},\ldots//. $$

Then

$$ X=\frac1{B_1+X_1}, \qquad X_1=\frac1{B_2+X_2}, \qquad \ldots $$

Since every $B_j\ge1$ and every $X_j>0$, we have $0<X_j<1$. Therefore

$$ B_{n+1}\le \frac1{X_n}<B_{n+1}+1, $$

hence

$$ \left\lfloor\frac1{X_n}\right\rfloor=B_{n+1}. $$

Applying definition (10) to $X=X_0$ yields $A_{n+1}=B_{n+1}$ for all $n\ge0$. Since an infinite regular continued fraction cannot represent a rational number, $X$ is irrational. Thus the regular continued fraction of $X$ is exactly $//B_1,B_2,\ldots//$.

Now let

$$ X=//B_1,\ldots,B_m//, \qquad B_m>1. $$

Put $X_0=X$ and define $X_n$ by (10). From

$$ X=\frac1{B_1+\frac1{B_2+\cdots+\frac1{B_m}}}, $$

a repeated application of (10) gives

$$ X_1=//B_2,\ldots,B_m//,\quad X_2=//B_3,\ldots,B_m//,\quad \ldots,\quad X_{m-1}=//B_m//= \frac1{B_m}. $$

For $0\le n<m-1$,

$$ 0<X_n<1, \qquad B_{n+1}\le \frac1{X_n}<B_{n+1}+1, $$

so $A_{n+1}=B_{n+1}$. Finally,

$$ \frac1{X_{m-1}}=B_m, $$

hence $A_m=B_m$ and

$$ X_m=\frac1{X_{m-1}}-A_m=0. $$

Therefore the regular continued fraction for $X$ terminates after $m$ partial quotients and has

$$ A_n=B_n\qquad(1\le n\le m). $$

This completes the proof.

∎