Chapter III
3.1.1 Preliminary Definition of Convergents A continued fraction can be terminated by retaining the terms a0; a1, a2, ··· , an and dropping all subsequent terms an+1, an+2, ···. The number obtained by this operation is called the nth convergent and denoted by pn/qn:
If a continued fraction is non-terminating, the sequence of the convergents is infinite. You do not yet know the meaning of non-terminating fractions, but this fact is not an obstacle to understanding convergents. For example, for the fraction [1; 2, 2, 2, ···], the sequence is
Hint: It is this fact (the possibility of forming convergents) which allows you to give meaning to non-terminating continued fractions and to assume that convergents are successive approximations which determine the value of a non-terminating continued fraction.
This is the seed from which the theory will grow. It will be developed in Chapter IV where it is proved that convergents of terminating continued fractions are successive approximations. Check now the truth of this statement for 61/27. In order to obtain approximations, note that 61/27 » 2.259.
Note that the errors form a sequence of terms with alternating signs and decreasing magnitude. It will be proved below that this is a general rule.
3.1.2 How to generate convergents There is no need to write out the stages of continued fractions and execute the tiresome process of successive evaluations, if yo want to find the nth convergent. There exist quite simple recursion formulae for estimating pn and qn*. Obviously,
*A formula which expresses an arbitrary element of a sequence in terms of one or several preceding elements is called a recursion formula. Thus, the nth term of a geometric progression is given by a recursion formula un=un+1q or by a non-recursion formula un=u1qn-1. A recursion formula does not allow immediate evaluation of un; you must find successively u1, u2, ··· , un.
In order to proceed from p1/q1 to p2/q2, you must replace a1 by a1 + 1/a2. You find
It has the structure
This formula reveals the general rule. The numerator and denominator of the nth convergent are:
Prior to proving (4), consider the meaning of these formulae. For the time being, no individual meaning will be attached to pn and qn (this restriction will be dropped in 3.1.3). The formulae (4) mean: You may take pn and qn, as well as values proportional to them, as the numerator and denominator of the nth convergent.
Proof by mathematical induction. Let the formulae apply for a certain fixed value n, say k,
and then prove that (4) above holds for n = k +1.
The expressions
show that you step over from pk/qk to pk+1/qk+1,by replacing ak by ak+1/ak+1. Carry out this substitution in (5) above. Note that pk-2, qk-2, pk-1/qk-1 do not change because they do not contain ak. You have
Since pk+1 and qk+1 are defined to within a factor of proportionality, drop the factor 1/ak+1 and replace the expression in brackets, using (5),
Hence you obtain (5) with k + 1 replacing k.
Moreover, it has already been seen that (4) holds for n = 2, Hence these formulae also hold for n = 2, 3, ··· , s, whence the recurrence relations hold.
3.1.3 Final Definition of Convergents The meaning of the term convergent can now be changed. Let p0/q0 and p1/q1 be the convergents of order zero and one, respectively, with p0 = a0, q0 = 1, p1 = a0a1 + 1, q1 = a1, that is, assume that the convergents of orders 2, 3, ··· , s are the fractions with the numerators and denominators given by (4) for n = 2, 3, ··· , s.
You may not have appreciated the change. Did we really use a different interpretation of convergents?
The point is that the same number can be written in different ways. For example, the notations 0.5, 1/2 and 2/4 represent the same number. So far the term nth convergent has been interpreted as a certain number regardless of the notation.
Thus, different answers could be given in the example of 2.1.2 to the question: What is the second convergent of 61/27?: 2¼, 2.25, 9/4, 18/8, etc. All of them represent the same number in different notations. However, from now on the term convergent will mean not only a definite number but also a prescribed notation of this number. This means that the convergent p2/q2 for 64/27 is 9/4, while 18/8 is false*. From now on, both the numerator and denominator of any convergent are defined strictly, not to within a proportionality factor (in the above example p2 = 9, q2 = 4).
* Note that 9/4 and 18/8 are indeed different fractions, even though they represent the same rational number.
This convention is very important for the further development of the theory of continued fractions.
Noting that all letters in the formulae (4) above are natural numbers, it will be readily understood that the denominators (as well as the numerators) of successive convergents strictly increase, that is, qn > qn-1, pn > pn-1 (n = 2, 3, ··· ). A comparison of p0, q0 with p1, q1 yields
p1 = p0 a1 + 1, q0 = 1, q1 = a1,
whence p1 > p0, while q0 may prove to equal q1. Finally,
The sequences (6) can be finite of infinite, depending on whether the continued fraction generating them terminates or not.
3.1.4 Evaluation of Convergents We will now present a convenient scheme for the evaluation of convergents. The values of the ai are presented in the first, those of the pi in the second and those of the qi in the third rows.
Start filling in the first row and the first two columns. You evaluate the entries in the order
1. the
column 
is multiplied by an; 2.
the new column is added to the preceding one.
The same scheme is recommended if you want to
compute the value of terminating continued fraction: The last
column 
contains the answer. This is much simpler than the
ierative approach.
Practice by filling in the table for the continued fraction [-; 3, 14, 1,2,5].
3.1.5 Complete quotients You will often want to terminate the process of expanding a number in a continued fraction before the computations end. For example,
or
The numbers 27/7 and 7/6 in these expressions are called the complete quotients (cf. below for the definition). The following notation is used:
that is, the complete quotient is separated from the preceding terms by a vertical bar.
The complete quotient an can be defined by
where
The complete quotient is thus a continued fraction which does not begin with a0, that is, it is the continued fraction the first n terms a0 to an of which have been cut off. The symbolic notation for (7) is
Complete quotients have the property: If certain complete quotients coincide, that is, an = an+k (k > 0), then, firstly, this repeats after every k steps:
an = an+k = an+2k = ··· = an+mk = ··· ,
and secondly, the continued fraction itself is non-terminating and periodic.
The proof is obvious and need not be presented. Only the first step will be described. When you apply the algorithm of expanding a number a into a continued fraction and come to some complete quotient an, the subsequent steps are independent of the preceding steps, that is, of the terms a0, a1, a2, ···, an-1. Hence the terms which follow an+k-1 in the continued fraction are the same which follow an-1.
If an is a natural number, then an = an, and the vertical bar in (9) can be replaced by a comma. It is logical to set a0 = a.
The continued fraction (8) above can be a terminating or a non-terminating fraction. The meaning of non-terminating continued fractions is explained in Chapter IV, so that we will deal for the time being formally with (8).
We can now derive a formula which relates complete quotients to convergents. Equation (7) reveals: If you drop 1/an on the right hand side, the remaining part of a is a convergent pn-1/qn-1 which by (4) can be rewritten
If you replace now an-1 by an+1+1/an, you reconvert the left hand side into a:
Finally,
3.2.1 Difference Between Two Neighbouring Convergents The step from the nth to the (n+1)th convergent is the increment of the nth convergent, denoted by Dn:
where Dn denotes the numerator
Use (4) to reduce the subscripts of pn+1 and qn+1 by 1:
The expression in brackets is of the same type as (11), but all subscripts are less by 1, whence it is equal to Dn+1:
Dn = - Dn-1.
This recursion relation allows you to reduce the subscript to zero:
The only step to total success is the direct evaluation of D0:
and, by (10),
3.2.2 Comparison of Neighbouring Convergents Note certain important properties of convergents.
Property 1 Each odd-numbered convergent is greater than its neighbouring convergents. Each even-numbered convergent is less than its neighbours.
When you test this behaviour, you must bear in mind that the 0th convergent and the last one (if it exists) have each only a single neighbour.
Equation (13) above proves directly that this property holds. Property 1 indicates that successive convergents alternate in being larger or smaller than their immediate successors.
Property 2 The absolute value of the difference between neighbouring convergents decreases with the increasing number of the convergent.
Proof:
It shows that qn+2 > qn, whence the denominator of the second fraction is greater and the fraction itself is smaller.
Property 3 The exact value of a terminating continued fraction a lies between any two neighbouring convergents. All even-numbered convergents lie to the left of a, that is, they give an approximation of a by defect. All odd-numbered convergents lie to the right of a, that is, they give an approximation of a by excess.
Obviously, the last convergent must be excluded since it is exactly equal to a.
We will not give
here a proof, but illustrate the main idea by Fig. 8, which shows the locations of the
convergents on the number line. The numbers do not indicate the
magnitudes but the location of each convergent. The point
furthest to the left is No. 0 convergent (i.e., the integer part
of the continued fraction). A step to the right is required to
move from No. 0 to No. 1. This step (i.e., D0) is shown by the upper arc.
In order to move from No. 1 to No. 2, you have to step towards
the left hand side, but this step (i.e., D1) is shorter than D0; then take another step,
etc. The steps are in turn towards the right and towards the
left, and each step is shorter than the preceding one. Fig. 8
shows that Property
3
applies.
Fig. 9 illustrates the relative arrangement of successive convergents. The abscissa gives the number of a convergent, the ordinate its magnitude. The dashed line is at the level of a.
Property 4 The absolute error of approximating the number a by a convergent pn/qn is less than 1/qn², that is,
Proof: By Property 3 and (13), you find that
This estimate is not convenient, because when approximating a » pn/qn, you may not know the next convergent. Hence we replace qn+1 in the last inequality by the smaller number qn and thereby only strengthen the inequality. This proves (14).
Property 4 shows that convergents are very good for approximating real numbers. If the fraction pn/qn were not a convergent, the absolute error would be |a - pn/qn| £ 1/2qn.
3.2.3 Irreducibility of convergents Consider one more property of convergents.
Property 5 All convergents are irreducible to lower terms.
The numerators and denominators of convergents are given by (4). Assume now that the fraction pn/qn can be reduced to lower terms, that is, the numerator and denominator have a common multiplier l other than unity:
pn
= l pn',
qn = l qn',
where pn' and qn' are natural numbers. Then (12) yields
This equality is absurd, because the left hand side is divisible by l, while the right hand side is not. Hence pn/qn is not reducible to lower terms.
A set of mutually equal fractions contains only one irreducible fraction. A convergent may thus be defined as follows: A convergent is the fraction, irreducible to lower terms, which gives the value of a truncated continued fraction.