Associated Topics || Dr. Math Home || Search Dr. Math

### Proving the Convergence of Continued Fractions

```
Date: 01/10/2001 at 09:27:29
From: Katy Fields
Subject: Continued Fractions

The Ask Dr. Math archive entry:

22/7 as an Approximation for Pi
http://mathforum.org/dr.math/problems/faulkner4.1.98.html"

assumes that the sequence of convergents

3 + 1/(7 + 1/(15 + 1/(1 + 1/(292 + 1/...))))

actually converges to pi.

How do you prove that the sequence actually converges?

What I'm looking for is something similar to the proof in elementary
calculus that the Taylor Series converges, a derivation of a formula
that provides an upper bound on the difference between the convergent
and the number toward which it converges.

If this question is beyond the scope of this website (I hope it
isn't!), please tell me which books on this subject cover this and do
so most clearly.

Thank you,
Katy
```

```
Date: 01/10/2001 at 17:06:24
From: Doctor Rob
Subject: Re: Continued Fractions

Thanks for writing to Ask Dr. Math, Katy.

The proof that the convergents to a simple continued fraction do
converge to the value you started with goes like this.

Let x be irrational, and let its simple continued fraction have the
form:

a[0] + 1/(a[1] + 1/(a[2] + 1/(a[3] + 1/(a[4] + 1/(a[5] + ...)))))

Now define

x[0]   = x
a[0]   = greatest integer in x[0]
p[-1]  = 1
q[-1]  = 0
p[0]   = a[0]
q[0]    = 1
x[n+1] = 1/(x[n]-a[n])
a[n+1] = greatest integer in x[n+1]
p[n+1] = a[n+1]*p[n] + p[n-1]
q[n+1] = a[n+1]*q[n] + q[n-1]

These definitions imply that a[n] >= 1 for all n >= 1. Then the nth
convergent to x is p[n]/q[n]. a[n] is called the nth partial quotient,
and x[n] is called the nth complete quotient. Then the simple
continued fraction of x is:

a[0] + 1/(a[1] + 1/(a[2] + 1/(a[3] + 1/(a[4] + 1/(a[5] + ...)))))

p[n]/q[n] is the fraction you get by truncating this fraction at the
point ... + 1/a[n])..., and simplifying. (This is the analogue of a
partial sum of an infinite series.) You can prove by induction that
for any value of n >= 0,

p[n]*q[n-1] - p[n-1]*q[n] = (-1)^(n-1)

You can also prove by induction that for all n >= 2,

q[n+1] >= q[n] + 1

This implies that as n -> infinity, q[n] -> infinity. You can also
prove by induction that

x = a[0] + 1/(a[1] + 1/(a[2] + ... + 1/(a[n-1] + 1/x[n])...))

Now you can prove that

p[0]/q[0] < p[2]/q[2] < ... < x < ... < p[3]/q[3] < p[1]/q[1]

Thus the even convergents are increasing, but always less than x, and
the odd convergents are decreasing, but always greater than x.

Now all you need to show is that the distance between consecutive
convergents approaches zero, that is,

lim    |p[n]/q[n]-p[n-1]/q[n-1]| = 0
n->infinity

lim    |p[n]*q[n-1]-p[n-1]*q[n]|/(q[n]*q[n-1]) = 0
n->infinity

lim    |(-1)^(n-1)|/(q[n]*q[n-1]) = 0
n->infinity

lim    1/(q[n]*q[n-1]) = 0
n->infinity

This last is a corollary of the fact that q[n] -> infinity as
n -> infinity.

That shows that the odd- and even-numbered convergents are approaching
each other, with x caught in between, so both must approach x. Thus

lim    p[n]/q[n] = x
n->infinity

(This is the analogue of the limit of the partial sums of a convergent
infinite series being set equal to the infinite sum.)

That is why it makes sense to write that an irrational number x equals
the infinite simple continued fraction, so:

x = a[0] + 1/(a[1] + 1/(a[2] + 1/(a[3] + 1/(a[4] + ...))))

By the way, if x is rational, the continued fraction will terminate.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 01/16/2001 at 11:12:56
From: Katy Fields
Subject: Re: Continued Fractions

Hi Doctor Rob.

I have absorbed your excellent and much appreciated proof that
convergents converge.

I respectfully submit that you might have overlooked a minor point
(see below) that has no effect on the conclusion.

Thank you again for your very generous help.

Sincerely,
Katy Fields

***** (Part I: Pointing out the applicable part of the proof)

The proof depends upon

q[n+1] >= q[n] + 1

which follows from

q[n+1] = a[n+1]*q[n] + q[n-1]

and

a[n+1] > 1 and q[n-1] > 1

where a[n+1] > 1 follows from the recursion relation that defines
x[n+1] as

x[n+1] = 1/(x[n]-a[n])

***** (Part II: Criticism of above)

Nothing precludes an arbitrary continued fraction from having one or
more terms equal to zero.  In other words, we cannot ignore a[n+1] =
0. To illustrate this point, I can generate such a continued fraction
from any other continued fraction by simply inserting a zero term
anywhere I like.

***** (Part III: Resolution)

This exception can be addressed using the following simple
"contraction" theorem, which allows us to replace any simple continued
fraction having one or more terms equal to zero by an equal simple
continued fraction whose terms are all non-zero.

A simple continued fraction with n terms, whose kth term is zero, is
equal to a simple continued fraction of two less terms (ie. n-2 terms)
that differs from the original simple continued fraction by replacing
three terms (the k-1st, kth, and k+1st terms) by one term equal to
their sum (a[k-1] + 0 + a[k+1]).

***** (Part IV: Corollary)

The above contraction theorem has the following simple corollary:

A simple continued fraction that has two consecutive terms that are
zero is equal to a simple continued fraction of two less terms that
differs from the original simple continued fraction by simply the
omission of the two zero terms.

***** (Part V: Questions)

If A[x] is the continued fraction that is generated from the real
number x by the usual recursive formula, what is x' = A[x, n, 0], the
value of the real number that results by inserting a zero before the
nth term of A[x]?

More generally, what is x' = A[x, n, z], the value of the real number
that results by inserting the integer value z before the nth term of
A[x]?

Similarly, what is x' = A[x, delete n], the value of the real number
that results by deleting  the nth term of A[x]?

And similarly, what is x' = A[x, n, substitute z], the value of the
real number that results by substituting (vs inserting) the integer
value z for the nth term of A[x]?

I appreciate that these are just a few of the questions that
mathematicians have addressed. Rather than try to reinvent all this
mathematics and stumble upon all the pitfalls along the way, I'd like
to find a clear exposition of it. In particular, my interest in this
field has been sparked by Calvin Clawson's book _Mathematical
Mysteries_, and I would like to find a book that would instruct me on
not just simple continued fractions but also general continued

One particular curiosity I'd like to address comes from the
realization that the general continued fraction generalizes the simple
continued fraction - which amounts to Euclid's GCD algorithm when the
real number we start with is rational. Since Euclid's GCD algorithm is
the basis for most of the elementary number theory I know, I assume
that the general continued fraction is the basis for much more. I'd
has been developed.
```

```
Date: 01/16/2001 at 12:41:36
From: Doctor Rob
Subject: Re: Continued Fractions

Thanks for writing back.

Continued fractions with 0 partial quotients after the first one
cannot occur by the process described. If

a[n+1] = 0 = Floor(x[n+1])

then

0 <=    x[n+1]     < 1
0 <= 1/(x[n]-a[n]) < 1

1 < x[n] - a[n]
a[n] < x[n] - 1
Floor(x[n]) < x[n] - 1
Floor(x[n]) + 1 < x[n]

which is impossible by the definition of the Floor (or greatest
integer) function. It is possible for a[0] <= 0, but for larger
subscripts for a[n], all these values must be 1 or larger.

This means that the case that was troubling you, but which you
resolved, is not an issue.

The only book that I know of that contains the information you seek
is written in German. It is _Die Lehre von Kettenbruche_, by Oskar
Perron. It seems likely that there are books in English covering this,
but I don't know about them.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search