One of the rare pleasures of doing mathematics — not necessarily high-powered research-level mathematics, but casual fun stuff too — is finally getting an answer to a question tucked away at the back of one’s mind for years and years, sometimes decades. Let me give an example: ever since I was pretty young (early teens), I’ve loved continued fractions; they are a marvelous way of representing numbers, with all sorts of connections to non-trivial mathematics [analysis, number theory (both algebraic and transcendental!), dynamical systems, knot theory, …]. And ever since I’ve heard of continued fractions, there’s one little factoid which I have frequently seen mentioned but which is hardly ever proved in the classic texts, at least not in the ones I looked at: the beautiful continued fraction representation for .

[Admittedly, most of my past searches were done in the pre-Google era — today it’s not that hard to find proofs online.]

This continued fraction was apparently “proved” by Euler way back when (1731); I once searched for a proof in his Collected Works, but for some reason didn’t find it; perhaps I just got lost in the forest. Sometimes I would ask people for a proof; the responses I got were generally along the lines of “isn’t that trivial?” or “I think I can prove that”. But talk is cheap, and I never did get no satisfaction. That is, until a few (maybe five) years ago, when by accident I spotted a proof buried in Volume 2 of Knuth’s The Art of Computer Programming. Huge rush of relief! So, if any of you have been bothered by this yourselves, maybe this is your lucky day.

I’m sure most of you know what I’m talking about. To get the (regular) continued fraction for a number, just iterate the following steps: write down the integer part, subtract it, take the reciprocal. Lather, rinse, repeat. For example, the sequence of integer parts you get for is 1, 2, 2, 2, … — this means

giving the continued fraction representation for . Ignoring questions of convergence, this equation should be “obvious”, because it says that the continued fraction you get for equals the reciprocal of the continued fraction for .

Before launching in on , let me briefly recall a few well-known facts about continued fractions:

- Every rational number has a continued fraction representation of finite length. The continued fraction expresses what happens when one iterates the Euclidean division algorithm.

For example, the integer parts appearing in the continued fraction for 37/14:

duplicate the successive quotients one gets by using the division algorithm to compute :

- A number has an infinite continued fraction if and only if it is irrational. Let denote the space of irrationals between 0 and 1 (as a subspace of ). The continued fraction representation (mapping an irrational to the corresponding infinite sequence of integer parts in its continued fraction representation ) gives a homeomorphism where carries a topology as product of countably many copies of the discrete space .

In particular, the shift map , defined by , corresponds to the map defined by . The behavior of is a paragon, an exemplary model, of **chaos**:

- There is a dense set of periodic points of . These are quadratic surds like : elements of that are fixed points of fractional linear transformations (for integral and ).
- The transformation is topologically mixing.
- There is sensitive dependence on initial conditions.

For some reason, I find it fun to observe this sensitive dependence using an ordinary calculator. Try calculating something like the golden mean , and hit it with over and over and watch the parade of integer parts go by (a long succession of 1’s until the precision of the arithmetic finally breaks down and the behavior looks random, chaotic). For me this activity is about as enjoyable as popping bubble wrap.

**Remark**: One can say rather more in addition to the topological mixing property. Specifically, consider the measure on , where . It may be shown that is a measure-preserving transformation; much more significantly, is an ergodic transformation on the measure space. It then follows from Birkhoff’s ergodicity theorem that whenever is integrable, the time averages approach the space average for almost all . Applying this fact to , it follows that for almost all irrationals , the geometric mean of the integer parts approaches a constant, Khinchin’s constant . A fantastic theorem!

Anyway, I digress. You are probably waiting to hear about the continued fraction representation of , which is :

Cute little sequence, except for the bump at the beginning where there’s a 2 instead of a 1. One thing I learned from Knuth is that the bump is smoothed away by writing it in a slightly different way,

involving triads , where .

Anyway, how to prove this fact? I’ll sketch two proofs. The first is the one I found in Knuth (*loc. cit.*, p. 375, exercise 16; see also pp. 650-651), and I imagine it is close in spirit to how Euler found it. The second is from a lovely article of Henry Cohn which appeared in the American Mathematical Monthly (Vol. 116 [2006], pp. 57-62), and is connected with Hermite’s proof of the transcendence of .

**PROOF 1 (sketch)**

Two functions which Euler must have been very fond of are the tangent function and its cousin the hyperbolic tangent function,

related by the equation . These functions crop up a lot in his investigations. For example, he knew that their Taylor expansions are connected with Bernoulli numbers, e.g.,

The Taylor coefficients where are integers called *tangent numbers*; they are the numbers 1, 2, 16, … which appear along the right edge of the triangle

1

0, 1

1, 1, 0

0, 1, 2, 2

5, 5, 4, 2, 0

0, 5, 10, 14, 16, 16

where each row is gotten by taking partial sums from the preceding row, moving alternately left-to-right and right-to-left. The numbers 1, 1, 5, … which appear along the left edge are called *secant numbers* , the Taylor coefficients of the secant function. Putting , the secant and tangent numbers together are called *Euler numbers,* and enjoy some interesting combinatorics: counts the number of “zig-zag permutations” of , where . For more on this, see Stanley’s Enumerative Combinatorics (Volume I), p. 149, and also Conway and Guy’s The Book of Numbers, pp. 110-111; I also once gave a brief account of the combinatorics of the in terms the generating function , over here.

Euler also discovered a lovely continued fraction representation,

as a by-product of a larger investigation into continued fractions for solutions to the general Riccati equation. Let’s imagine how he might have found this continued fraction. Since both sides of the equation are odd functions, we may as well consider just , where . Thus the integer part is 0; subtract the integer part and take the reciprocal, and see what happens.

The MacLaurin series for is ; its reciprocal has a pole at 0 of residue 1, so

gives a function which is odd and analytic near 0. Now repeat: reciprocating , we get a simple pole at 0 of residue 3, and

gives a function which is odd and analytic near 0, and one may check by hand that its MacLaurin series begins as .

The pattern continues by a simple induction. Recursively define (for )

It turns out (lemma 1 below) that each is odd and analytic near 0, and then it becomes plausible that the continued fraction for above is correct: we have

Indeed, assuming the fact that is uniformly bounded over , these expressions converge as , so that the continued fraction expression for is correct.

**Lemma 1**: Each (as recursively defined above) is odd and analytic near 0, and satisfies the differential equation

**Proof**: By induction. In the case , we have that is analytic and

Assuming the conditions hold when , and writing

we easily calculate from the differential equation that . It follows that

is indeed analytic in a neighborhood of 0. The verification of the differential equation (as inductive step) for the case is routine and left to the reader.

**Remark**: The proof that the continued fraction above indeed converges to is too involved to give in detail here; I’ll just refer to notes that Knuth gives in the answers to his exercises. Basically, for each in the range , he gets a uniform bound for all , and notes that as a result convergence of the continued fraction is then easy to prove for such (good enough for us, as we’ll be taking ). He goes on to say, somewhat telegraphically for my taste, “Careful study of this argument reveals that the power series for actually converges for ; therefore the singularities of get farther and farther away from the origin as grows, and the continued fraction actually represents*throughout*the complex plane.” [Emphasis his] Hmm…

Assuming the continued fraction representation for , let’s tackle . From the continued fraction we get for instance

Taking reciprocals and manipulating,

**Theorem 1**: .

**Proof**: By the last displayed equation, it suffices to show

This follows from a recursive algorithm for multiplying a continued fraction by 2, due to Hurwitz (Knuth, *loc. cit.*, p. 375, exercise 14):

**Lemma 2**: , and

I won’t bother proving this; instead I’ll just run through a few cycles to see how it applies to theorem 1:

and so on. Continuing this procedure, we get , which finishes the proof of theorem 1.

**PROOF 2**

I turn now to the second proof (by Cohn, *loc. cit.*), which I find rather more satisfying. It’s based on Padé approximants, which are “best fit” rational function approximations to a given analytic function, much as the rational approximants provide “best fits” to a given real number . (By “best fit”, I mean a sample theorem like: among all rational numbers whose denominator is bounded above in magnitude by , the approximant comes closest to .)

**Definition**: Let be a function analytic in a neighborhood of 0. The *Padé approximant* to of order , denoted , is the (unique) rational function such that , , and the MacLaurin coefficients of agree with those of up to degree .

This agreement of MacLaurin coefficients is equivalent to the condition that the function

is analytic around 0. Here, we will be interested in Padé approximants to .

In general, Padé approximants may be computed by (tedious) linear algebra, but in the present case Hermite found a clever integration trick which gets the job done:

**Proposition 1**: Let be a polynomial of degree . Then there are polynomials of degree at most such that

Explicitly,

**Proof**: Integration by parts yields

and the general result follows by induction.

It is clear that the integral of proposition 1 defines a function analytic in . Taking , this means we can read off the Padé approximant to from the formulas for in proposition 1, provided that the polynomial [of degree ] is chosen so that . Looking at these formulas, all we have to do is choose to have a zero of order at , and a zero of order at . Therefore fits the bill.

Notice also we can adjust by any constant multiple; the numerator and denominator are adjusted by the same constant multiples, which cancel each other in the Padé approximant .

Taking in proposition 1, we then infer

Notice that this integral is small when are large. This means that will be close to (see the following remark), and it turns out that by choosing appropriately, the values coincide exactly with rational approximants coming from the continued fraction for .

**Remark**: Note that for the choice , the values derived from proposition 1 are manifestly integral, and . [In particular, , justifying the claim that is small if is.] In fact, may be much larger than necessary; e.g., they may have a common factor, so that the fraction is unreduced. This ties in with how we adjust by a constant factor, as in theorem 2 below.

For , let denote the rational approximant arising from the infinite continued fraction

where . From standard theory of continued fractions, we have the following recursive rule for computing the integers from the : , , , , and

Explicitly, and , so

[Note: and , so is infinite, but that won’t matter below.]

**Theorem 2**: Define, for ,

Then , , and .

**Proof**: It is easy to see , , and . In view of the recursive relations for the above, it suffices to show

The last relation is trivial. The first relation follows by integrating both sides of the identity

over the interval . The second relation follows by integrating both sides of the identity

which we leave to the reader to check. This completes the proof.

Theorem 2 immediately implies that

indeed, the rational approximants to the right-hand side have the property that is one of , or (for respectively), and looking at their integral expressions, these quantities approach 0 very rapidly.

This in turn means, since the denominators grow rapidly with , that the rational approximants approach “*insanely*” rapidly, and this in itself can be used as the basis of a proof that is transcendental (Roth’s theorem). To give some quantitative inkling of just “how rapidly”: Knuth in his notes gives estimates on how close the approximant

is to the function . It’s something on the order of (*loc. cit.*, p. 651).

**Remark**: Quoting Roth’s theorem in support of a theorem of Hermite is admittedly anachronistic. However, the Padé approximants and their integral representations used here did play an implicit role in Hermite’s proof of the transcendence of ; in fact, Padé was a student of Hermite. See Cohn’s article for further references to this topic.

[*Wow, another long post. I wonder if anyone will read the whole thing!*]

[Edits in response to the comment below by Henry Cohn.]

## 23 comments

Comments feed for this article

August 4, 2008 at 3:12 pm

anonI read the whole thing; it was extremely informative!

In connection with Hermite, it seems appropriate to note that besides the obvious appearance of continued fractions in number theory; they also play a beautiful theory in the classical theory of orthogonal polynomials (and thereby to deep modern results in the theory of random matrices – a good reference, despite the plethora of typos, is the Courant Institute notes by Deift).

Hermite’s interest in special functions was, of course, legendary…

August 4, 2008 at 10:48 pm

Todd Trimbleanon: I was not really aware of this. I would describe my involvement in this area as something like a mathematician’s casual interest, certainly nowhere near the level of a professional special function theorist’s.

Still, your comment (and the August 2 post of Terence Tao, also on random matrices and connections with orthogonal polynomials) is somewhat intriguing to me — you seem to be hinting that there exists a much more conceptual point of view on the material touched upon in this post, which would be very welcome to me. For example, there seem to be some intriguing hints about this in the Wikipedia article on orthogonal polynomials, under headings like Recurrence Relations and the Rodrigues Formula, but I haven’t found much time to think about this yet.

Similarly, from what little I was able to glean so far from the Google Books result, the book by Deift also is promoting a pretty high-level point of view (Riemann-Hilbert correspondence, etc.). The books I have at home on special functions, notably Special Functions by Andrews, Askey and Roy and also Whittaker & Watson, are not in that style [and have little on continued fractions] — they are good, but have a kind of 19th or early 20th century feel to them, and are hard for me to really get into.

August 14, 2008 at 2:47 pm

Anonymousi watched a nice talk by arnold on continued fractions at msri (www.msri.org/communications/vmath/index_html )

there is also a set of notes by gasper. both of these are what i

would consider novel way of looking at the continued fraction.

one day i will read both of them.

August 18, 2008 at 4:07 am

John BaezWow! I hadn’t known you liked continued fractions, Todd. But with your fondness for them, you’ve

gotto take a look at this book:Claude Brezinski,

History of Continued Fractions and Pade ApproximationsSpringer-Verlag: New York, 1980.It goes

wayback and presentslotsof fascinating calculations and tricks. It’s 559 pages long – one of those works of fanatic devotion that’s extremely admirable, fun to dip into, but kind of leaves you wondering what makes the author tick.Chapter 4 is about “the golden age” of continued fraction, starting with the work of Euler. Interestingly, a certain amount of Euler’s work on continued fractions involved his attempt to sum the divergent series

0! – 1! + 2! – 3! + 4! – …

He was able to convert it into a continued fraction and then estimate its value at

0.5963475922

This makes me smile a bit when you question Knuth’s rigor. 🙂

But as usual, Euler was on to something: we can probably understand this calculation if we ponder the asymptotic series for the function Wikipedia calls E_1(x), a relative of the “exponential integral” function Ei(x).

I’ve always found this asymptotic series hilarious: apart from minor fudge factors, it’s basically

0! + 1!/x + 2!/x^2 + 3!/x^3 + …

A dislexic parody of the usual exponential function!

Anyway, this is but one of the gems buried in Brezinski’s enormous treasure chest.

(Far be it from me to encourage those Byelorussian scofflaws, but I can’t help but notice that Brezinski’s book is available as part of their enormous online collection of free math and physics books, in djvu format.)

August 18, 2008 at 4:08 am

John BaezDamn! I spelled “dyslexic” wrong! 🙂

August 18, 2008 at 5:32 am

Todd TrimbleThanks for the reference, John! Yes, I’ll have to get hold of that book.

That Wikipedia article has some funny mathematical English in it; if I knew Russian, I’d be tempted to translate it into Russian and back into English and see what happens. 🙂

Free associating a little, that “dyslexic exponential” puts me in mind of the asymptotic series underlying Stirling’s formula, which also leads (curiously, to my mind) to divergent series. You probably know what I mean: one can get finer and finer approximations to log(n!) by applying the Euler summation formula. Formally, one then gets

which gives simply fantastic approximations for large n,

provided you remember to truncate the series after finitely many terms, because the damn thing diverges very badly for all n if you take the whole infinite series (the n-th coefficient of being where denotes the k-th Bernoulli number).How

doyou derive that “dyslexic exponential” asymptotic series for the exponential integral? I’m probably being thrown off track, but the scent is reminiscent to me of the Euler summation formula, somehow…August 18, 2008 at 5:46 am

Todd TrimbleAnswering my own last question, I seem to find a derivation of the series here.

August 21, 2008 at 5:06 am

Henry CohnChrystal’s Textbook of Algebra is a great source of information on these sorts of things, although it is exceedingly old-fashioned. Paragraph 21 in Chapter 34 explains the continued fraction expansions of tan and tanh, and it gives Legendre’s version of Lambert’s proof of the irrationality of pi. I love that proof, since I find it far better motivated than most modern proofs. By contrast, Niven’s proof is shorter, but only because there’s so little context.

One thing I’ve always enjoyed about the Riccati equation approach is that it lets you evaluate any continued fraction whose partial quotients form an arithmetic progression. For example, [1,2,3,…] = I_0(2)/I_1(2), where I denotes the Bessel I function. More generally, [n+1,n+2,n+3,…] = I_n(2)/I_(n+1)(2), which is the key to the recursive analysis.

By the way, I don’t think you can deduce the transcendence of e from Roth’s theorem applied to the continued fraction (the partial quotients don’t grow nearly rapidly enough).

August 21, 2008 at 7:14 am

Todd TrimbleHenry Cohn: Thanks for your excellent comments! I’ll edit the bit about Roth’s theorem at the end (a slip on my part).

Naturally, I wasn’t aware of Chrystal’s text (from the late 19th century). Speaking of the continued fraction expansion of tanh(z), I was wondering whether the partial quotients (as rational functions) provide Padé approximants to this function. Also I am still puzzled about the domain of validity of this continued fraction expansion; Knuth claims it holds throughout the complex plane, but I wasn’t quite able to follow his hints, and was wondering why you could push past (since there are poles there). This being Knuth, I assume I’m just missing something.

John Baez recommended Brezinski’s book; are there any recent books you’d recommend?

August 22, 2008 at 5:23 am

Henry CohnThe partial quotients of the tanh continued fraction are almost Pade approximants. They are rational functions with one additional restriction, namely that their numerators are odd and their denominators are even. They match as many coefficients of tanh(x) as possible given this constraint and their degrees. You get actual Pade approximants for a related function after a change of variables (dividing by x and then replacing x^2 with x).

As for boundedness of f_n(x), one way to see it is to rewrite f_n(x) in a different form. Define g_n(x) as follows:

g_n(x) = 1 + x^2/(1!*(4n+2)) + x^4/(2!*(4n+2)*(4n+6)) + x^6/(3!*(4n+2)*(4n+6)*(4n+10)) + …

Then one finds that f_n(x) = g_(n+1)(x)/g_n(x)*x/(2n+1) (this is not hard to verify by induction).

Now we just need to bound g_(n+1)(x)/g_n(x). For every compact subset of the complex plane, g_n(x) stays arbitrarily close to 1 over that set as long as n is large enough. That suffices to bound f_n(x) (although it’s probably overkill).

As for books, unfortunately, I’m not really familiar with any recent books on continued fractions. Jones and Thron is a pretty useful reference for analytic questions, and Wall is also good, but I’ve never studied either one carefully.

By the way, here’s my favorite application of the tanh continued fraction: exp(sqrt(2)) is irrational. Consider sqrt(2)*(exp(sqrt(2))-1)/(exp(sqrt(2))+1). If exp(sqrt(2)) were rational, or even in Q(sqrt(2)), then this expression would be in Q(sqrt(2)). However, it is sqrt(2)*tanh(1/sqrt(2)), and the tanh continued fraction shows that this equals [0,1,6,5,14,9,22,13,…]. If it were in Q(sqrt(2)), it would have a periodic simple continued fraction expansion, but it doesn’t.

August 23, 2008 at 2:13 am

Todd TrimbleWow, Henry, you are just a font of good information! Thanks particularly for your response to the question about bounding f_n(x); I’m a lot happier now.

Ever think of writing a book on continued fractions yourself? An anonymous commenter above mentioned some notes by Gasper (George, I guess, unless it was a slip for

Gosper), which I wasn’t able to find. Gosper has been proselytizing for years the utility of continued fractions, and I think it would be great if they were more in the mainstream.August 23, 2008 at 6:39 am

Henry CohnNope, no plans for a book. I think it would be hard to write a book about continued fractions that would be both cohesive and reasonably comprehensive, since many of the subfields are really different from each other. There’s formal algebra, rational approximation theory, real quadratic number fields, convergence theory (which gets incredibly hairy for complex continued fractions), expansions of special functions, dynamical systems and ergodic theory, geometry of numbers, and probably several other areas I’m overlooking. A treatment aimed at specialists can focus on specific topics, but most readers would probably rather learn a little bit about each of these topics. One solution would be to have a bunch of somewhat independent chapters, but it doesn’t sound so appealing to me. In any case, I don’t think I’ve got enough perspective to do it justice.

By the way, Google book search has both Perron’s Lehre von den Kettenbruechen and volume 2 of Chrystal’s Textbook of Algebra (which has the continued fraction stuff – curiously, volume 1 is not there). It’s convenient that so much of the theory is old enough to be covered in books that are out of copyright, and they are both good books.

August 26, 2008 at 2:09 pm

Rational Tangles « Todd and Vishal’s blog[…] 26, 2008 in Math Topics | Tags: continued fractions | by Todd Trimble In my post, I made a comment in passing that continued fractions have applications to knot theory. Now <a […]

August 28, 2008 at 9:54 pm

Américo TavaresTwo recent books on Continued Fractions:

Continued Fractions with Applications (Studies in Computational Mathematics) by L. Lorentzen and H. Waadeland, North Holland, 1992

http://www.amazon.com/Continued-Fractions-Applications-Computational-Mathematics/dp/0444892656/ref=sr_1_3?ie=UTF8&s=books&qid=1219959362&sr=8-3

and

Orthogonal Polynomials and Continued Fractions by Sergey Khrushchev, Cambridge University Press, 2008

http://assets.cambridge.org/97805218/54191/frontmatter/9780521854191_frontmatter.pdf

(this one I have not seen it yet, but I know it also covers the Bauer-Muir Transformation I am interested in)

I hope this may help.

August 28, 2008 at 10:18 pm

Todd TrimbleThanks, Américo. Judging from the table of contents, the second book looks interesting, and I wouldn’t mind having a closer look.

I wasn’t able to find out much from Amazon about the first book (and at 210 US dollars, I wasn’t in much of a mood to purchase it). Would you be able to say something about the intended audience and point of view of this book?

August 28, 2008 at 11:09 pm

Américo TavaresThe chapters’ names are

I Introductory examples

II More basics

III Convergence criteria

IV Continued fraction and three-term recurrence relations

V Correspondance of continued fractions

VI Hypergeometric functions

VII Moments and orthogonality

VIII Padé approximants

IX Some applications in number theory

X Zero-free regions

XI Digital filters and continued fractions

XII Applications to some differential equations

Appendix. Some continued fraction expansions

This book belongs to the Studies in Computational Mathematics 3.

Prof. Lisa Lorentzen (University of Trondheim, Norway) has many research papers on continued fractions.

Prof. Bruce Berndt and other research mathematicians put this book as a reference in their papers on continued fractions, e. g.

http://www.math.uiuc.edu/~berndt/articles/rrcf.pdf

The price is indeed very high.

August 28, 2008 at 11:37 pm

Todd TrimbleThanks for the details, Américo — I appreciate it!

October 2, 2008 at 4:31 pm

Almost a problem of the week « Todd and Vishal’s blog[…] and square is a fun little exercise in number theory, involving Pell’s equation and (yes) continued fractions. I’ll sketch how this goes. We are trying to solve the Diophantine […]

January 2, 2011 at 6:28 am

2010 in review « Todd and Vishal’s blog[…] The busiest day of the year was January 20th with 196 views. The most popular post that day was Continued fraction for e. […]

January 10, 2011 at 7:28 am

Not all best rational approximations are the convergents of the continued fraction! « The Lumber Room[…] and e is (proved here). […]

February 5, 2011 at 7:44 pm

san francisco party busProblem solved

April 18, 2012 at 2:12 pm

izlehttp://www.izledinle.org/

really mixed problem. But you solved. Fine

September 7, 2013 at 5:50 pm

Cellulite Factor System free downloadIt goes without saying that performing cellulite massages

while using anti-cellulite products can yield better results.

The paleolithic eating plan explores and recommends eating like a caveman

where lean proteins, nuts and seeds, and green colorful low glycemic carbohydrates kept

inflammation and cancers at bay. These treatments and may cause in a range of $3000.