Proving the Convergence of Continued FractionsDate: 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 fractions, continued radicals, etc. 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 like to learn more about how the theory of general continued fractions 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/ |
Ask Dr. MathTM
© 1994-2002 The Math Forum
http://mathforum.org/dr.math/