Continued Fractions and the Euclidean Algorithm

5 The symbol

For arbitrary real numbers with each for j ≥ 2 the symbol
is defined recursively by:

In order for this definition to make sense one needs to know that the denominator in the
right -hand side of (1) is non-zero. The condition for j ≥ 2 guarantees, in fact, that
, as one may prove using induction.

It is an easy consequence of mathematical induction that the symbol is a rational
number if each is rational. In particular, each finite continued fraction is a rational number .
(Note that the symbol is to be called a continued fraction, according to the
convention of the first section, only when each is an integer.)

Observe that the recursive nature of the symbol suggests that the symbol should
be computed in a particular case working from right to left. Consider again, for example, the
computation above showing that [2, 3, 5, 2] = 81/35. Working from right to left one has:



There is, however, another approach to computing . Let, in fact, be
any (finite or infinite) sequence of real numbers. One uses the double recursion



to define the sequence , j ≥ − 1. The double recursion, differently initialized ,



defines the sequence , j ≥ − 1. Note that and ,


One now forms the matrix



Thus, for example,
 

and

It is easy to see that the matrices satisfy the double recursion

as a consequence of the double recursion formulas for the and . Hence, a simple argument
by mathematical induction shows that

This is summarized by :

Proposition 1. For any sequence , j ≥ 1 of real numbers, if and are the
sequences defined by the double recursions (2) and (3), then one has the matrix identity

for each integer r ≥1.

Corollary 1. One has the identity for each integer r ≥1.

Proof. The number is the determinant of the matrix . From the formula
(6) the matrix is the product of r matrix factors , each of which has determinant −1. Since
the determinant of the product of matrices is the product of the determinants of the factors, it
is clear that .

Corollary 2. One has the vector identity

for each integer r ≥1.

Proof. First recall (i) that the product of a matrix and a (column) vector is defined by the
relation

(ii) that the transpose of a matrix is the matrix whose rows are the columns of the given matrix,
and (iii) that the transpose operation reverses matrix multiplication. One tranposes both sides
of the relation (7) to obtain:

To this relation one applies the principle that the first column of any 2×2 matrix is the product
of that matrix with the column

in order to obtain the column identity (8).

Theorem 2. For any sequence , j ≥ 1 of real numbers, if and are the sequences
defined by the double recursions (2) and (3), and if for j ≥ 2, then the value of the
symbol is given by the formula

Proof. What is slightly strange about this important result is that while the and the
are defined by the front end recursions, albeit double recursions, (2) and (3), the symbol
is defined by the back end recursion (1). The proof begins with the comment that
the right-hand side of (10) does not make sense unless one can be sure that the denominator
. One can show easily by induction on r that for r ≥1 under the hypothesis
for j ≥ 2.

The proof proceeds by induction on r. If r = 1, the assertion of the theorem is simply the
statement , and, as noted above, and . Assume now that r ≥ 2.
By induction we may assume the correctness of the statement (10) for symbols of length r − 1,
and, therefore, for the symbol . That case of the statement says that
must be equal to a/c , where by corollary 2

with

Now by (1)

But by corollary 2 again

Hence,

6 Application to Continued Fractions

Recall that is called a continued fraction only when each is an integer and
for j ≥ 2. The sequence may be finite or infinite. The symbol
formed with the first r terms of the sequence , is called the r^th convergent of the
continued fraction. Associated with a given sequence are two sequences
and that are given, according to the double recursions (2), (3) of the previous section
with .

Proposition 2. If is a continued fraction, then the integers and are coprime
for each r ≥1.

Proof. By Corollary 1 of the previous section . Hence, any positive
divisor of both and must divide the left-hand side of this relation, and, therefore, must
also divide (−1)^r.

Proposition 3. The difference between successive convergents of the continued fraction
is given by the formula

Proof. According to the theorem (formula 10) at the end of the last section the convergent
is given by

Hence,

(The last step is by Corollary 1 above.)

Remark 1. The formula (11) remains true if where the are real numbers
subject to the assumption for j ≥1.

Lemma. The sequence is a strictly increasing sequence for j ≥ 2.

Proof. This is easily proved by induction from the recursive definition (3) of the sequence.

Theorem 3. If is an infinite continued fraction, then the limit

always exists.

Proof. As one plots the convergents on the line of real numbers, one moves alternately right
and left. The formula (11) for the difference between successive convergents elucidates not only
the fact of alternate right and left movement but also the fact that each successive movement
is smaller than the one preceding. Therefore, one has



Since any strictly increasing sequence of positive integers must have infinite limit, the seqence
has infinite limit, and so the sequence of reciprocals must converge to zero .
Hence, the sequences of odd- and even-indexed convergents must have the same limit, which is
the limit of the sequence of all convergents.

Definition 1. The limit of the sequence of convergents of an infinite continued fraction is called
the value of that continued fraction.

Theorem 4. If is the continued fraction expansion of an irrational number x, then



that is, the value of the continued fraction expansion of a real number is that real number.

Proof. For each r ≥1 the continued fraction expansion of x is characterized by
the identity



where is a real number with . The sequences of p’s and q’s for the symbol
agree with those for the symbol except for the r^th terms.
One has by (10)


where by (3)



Hence,


Therefore, the displacement from to x is by (11)



which is in the same direction but of smaller magnitude than the displacement from to
. Therefore, x must be larger than every odd-indexed convergent and smaller than every
even-indexed convergent. But since all convergents have the same limit, that limit must be x.