convergents to a continued fraction

Definition. The nth convergentMathworldPlanetmathPlanetmath to a continued fractionDlmfMathworldPlanetmath [a0,a1,a2,a3,] is the value of the fraction obtained by cutting off the fraction after an, i.e. the value of [a0,a1,,an].


p0 =a0 p1 =a0a1+1
q0 =1 q1 =a1

so that


For n>1, define

pn =anpn-1+pn-2 (1)
qn =anqn-1+qn-2
Theorem 1.

The nth convergent to [a0,a1,a2,a3,] is given by


where pn,qn are defined as above.


Induction. For n>1,

[a0,,an-1,an] =[a0,,an-1+1an]

Theorem 2.

For n1, the numbers pn-1qn-1 and pnqn are a Farey pair; in fact,

pnqn-1-pn-1qn=(-1)n-1 (2)

and thus

pnqn-pn-1qn-1=(-1)n-1qn-1qn (3)

This is again a simple induction. The statement is true for n=1. For n>1, we have

pnqn-1-pn-1qn =(anpn-1+pn-2)qn-1-pn-1(anqn-1+qn-2)

Note that if [a0,a1,] is a simple continued fraction, then the above theorem implies that gcd(pn,qn)=1, since any common factor of pn and qn must divide (-1)n.

Theorem 3.

For n2,

pnqn-2-pn-2qn=(-1)nan (4)
pnqn-pn-2qn-2=(-1)nanqn-2qn (5)

Similar to the proof of the above theorem. ∎

Theorem 4.

If [a0,a1,] is a simple continued fraction, then qnn and, for n>3, qn>n.


This follows directly from the iterative definition for the qi and the fact that the ai are positive integers. ∎

These results easily imply the following important convergence theorem:

Theorem 5.

For any continued fraction, the even convergents p2n/q2n are strictly monotonically increasing, and the odd convergents p2n+1/q2n+1 are strictly monotonically decreasing. In addition, every odd convergent is greater than each even convergent. If the continued fraction is simple, then the limit of the odd convergents is equal to the limit of the even convergents, and thus the continued fraction has a well-defined value equal to their common limit.


This is basically obvious from the previous observations. Write cn for the nth convergent, i.e.


Each qi is positive, so


is positive for n even and negative for n odd. This proves the observations about monotonicity. Also,


is positive for n odd, so that

c2n+1>c2n (6)

Now, if for some j,k we had c2j+1c2k, then jk by (6). If k<j, then since the even convergents increase, c2j+1c2k<c2j, while if j<k, then since the odd convergents decrease, c2k+1<c2j+1<c2k. In either case, this contradicts (6).

As to the statement about simple continued fractions, it is clear that the even (odd) convergents converge since they form a monotonically increasing (decreasing) sequenceMathworldPlanetmath that is bounded below (above). But


and thus the limits are identical. ∎

Next we prove the following theorem regarding the connection between the “tail” of a continued fraction, its convergents, and its value:

Theorem 6.

If x=[a0,a1,] is a simple continued fraction, write tn=[an,an+1,] for n0 (the nth complete convergent). Then


This is another simple proof by induction. Note that


so that




Finally, we derive a bound on how well the convergents approximate the value of the continued fraction:

Theorem 7.

If x=[a0,a1,] is a simple continued fraction, then

x-pnqn =pn-1+tn+1pnqn-1+tn+1qn-pnqn

But tn+1>an+1, so that qn-1+tn+1qn>qn-1+an+1qn=qn+1 and thus


since the qi are strictly increasing. ∎


  • 1 G.H. Hardy & E.M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Oxford Science Publications, 1979.
Title convergents to a continued fraction
Canonical name ConvergentsToAContinuedFraction
Date of creation 2013-03-22 18:04:20
Last modified on 2013-03-22 18:04:20
Owner rm50 (10146)
Last modified by rm50 (10146)
Numerical id 8
Author rm50 (10146)
Entry type Theorem
Classification msc 11Y65
Classification msc 11J70
Classification msc 11A55
Defines convergent
Defines complete convergent