Try our Free Online Math Solver!

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
righthand side of (1) is nonzero. 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 righthand 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 lefthand 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 evenindexed 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 oddindexed convergent and smaller
than every
evenindexed convergent. But since all convergents have the same limit, that
limit must be x.
Prev  Next 