Tag Archive

You are currently browsing the tag archive for the ‘continued fractions’ tag.

Almost a problem of the week

September 28, 2008 in Elementary Math Problem Solving, Problem of the Week (POW) | Tags: continued fractions, generating functions, pell's equation | by Todd Trimble | 4 comments

It’s been quite a while since I’ve posted anything; I’ve been very busy with non-mathematical things this past month, and probably will be for at least another few weeks. In the meantime, I’d been idly thinking of another Problem of the Week to post, and while I was thinking of one such problem… I got stuck. So instead of just baldly posing the problem, this time I’ll explain how far as I got with it, and then ask you all for help.

The problem is easy to state: except for 1, are there any positive integers which are simultaneously triangular, square, and pentagonal numbers?

Just asking for all numbers which are simultaneously triangular 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 equation

$\displaystyle m^2 = \frac{n(n+1)}{2}$

By completing the square and manipulating a little, we get

$8m^2 = (2n+1)^2 - 1.$

This converts to a Pell equation $x^2 - 2y^2 = 1$ where $x = 2n+1$ , $y = 2m$ . Writing the Pell equation as

$N(x + \sqrt{2}y) := (x + \sqrt{2}y)(x - \sqrt{2}y) = 1,$

and using the fact that the norm map $N: \mathbb{Q}(\sqrt{2}) \to \mathbb{Q}$ just defined is a multiplicative homomorphism (because the Galois automorphism $x + \sqrt{2}y \mapsto x - \sqrt{2}y$ is also multiplicative), we see that the set of solutions

$\{(x, y): N(x + \sqrt{2}y) = 1\}$

forms a group, under the group multiplication law

$(x, y) \cdot (x', y') = (x x' + 2y y', x y' + y x')$

which is read off just by expanding $(x + \sqrt{2}y)(x' + \sqrt{2}y')$ . The right branch of the hyperbola $x^2 - 2y^2 = 1$ thus forms a group (under this multiplication law, with identity $(1, 0)$ ) which is isomorphic to the additive group of real numbers. The set of integer solutions sitting on this branch forms a discrete subgroup, and hence is isomorphic to the additive group of integers (provided that nontrivial solutions exist!). To find a generator of this group, just look for the integer solutions to $x^2 - 2y^2 = 1$ which come closest to the identity $(1, 0)$ ; they are $(x, y) = (3, 2), (3, -2)$ .

So, $(3, 2)$ generates the set of positive integer solutions. The next is

$(3, 2)^2 = (3 \cdot 3 + 2(2 \cdot 2), 3 \cdot 2 + 2 \cdot 3) = (17, 12)$

and in general, the solutions $(x_n, y_n) = (3, 2)^n$ are given recursively by

$(x_n, y_n) = (3x_{n-1} + 4y_{n-1}, 2x_{n-1} + 3y_{n-1}).$

Let’s go back a minute to our original problem, which asked for numbers which are both triangular and square. We read off the $k^{th}$ triangle-square, $m_k^2 = n_k(n_k+1)/2$ , from $(x_k, y_k) = (2n_k + 1, 2m_k)$ . For example,

$(x_2, y_2) = (17, 12) \Rightarrow (n_2, m_2) = (8, 6)$

and so the square $36 = 6^2$ is simultaneously the triangular number $1 + 2 + \ldots + 8$ . From $(x_3, y_3) = (99, 70)$ , we have $(m_3, n_3) = (49, 35)$ , and so $35^2$ is the next triangle-square. The next after that is $204^2$ . And so on.

It would be nice to express these solutions in closed form. To this end, let me observe that the quotients $x_k/y_k = 3/2, 17/12, 99/70, \ldots$ are rational approximants to the continued fraction of $\sqrt{2}$ :

$3/2 = 1 + 1/2,$

$17/12 = 1 + 1/(2 + 1/(2 + 1/2)),$

$99/70 = 1 + 1/(2 + 1/(2 + 1/2 + 1/(2 + 1/2), \ldots$

(A similar observation applies to any Pell equation: positive solutions to $x^2 - Dy^2 = 1$ , where $D$ is square-free, can be read off by examining every other rational approximant to the continued fraction for $\sqrt{D}$ . This, I find, is a very cool fact.)

Starting from the first two rational approximants $p_0/q_0 = 1/1, p_1/q_1 = 3/2$ , the remaining approximants $p_k/q_k$ can be read off from the recursive rule (*)

$p_{k+1} = 2p_k + p_{k-1} \qquad q_{k+1} = 2q_k + q_{k-1}$

and for the purpose of determining the triangle-squares, we are really interested only in every other one of the denominators $q_k$ , that is to say, $q_1, q_3, q_5, \ldots$ . We can get a recursive rule for these from

$q_{k+2} = 2q_{k+1} + q_k = 2(2q_k + q_{k-1}) + q_k = 6q_k - q_{k-2}$

where the last equation follows easily from the recursive rule (*). The same recursion thus gives the $y_k$ and $m_k$ :

$y_k = 2, 12, 70, 408, \ldots,$

$m_k = 1, 6, 35, 204, \ldots,$

namely $m_k = 6m_{k-1} - m_{k-2}$ .

To get a closed form for the $m_k$ (whose squares are triangular), we can now apply the familiar method of generating functions (see here for a worked example of this method to derive the closed form for the Fibonacci numbers). Form

$f(x) = m_1 + m_2 x + m_3 x^2 + \ldots = 1 + 6x + 35x^2 + \ldots$

and use the recursive rule for the $m_k$ to deduce (after some manipulation) that

$\displaystyle f(x) = \frac1{1 - 6x + x^2}.$

The denominator expands as $(1 - (3 + \sqrt{8})x)(1 - (3 - \sqrt{8})x)$ ; by the method of partial fractions, we obtain

$\displaystyle f(x) = \frac{(3 + \sqrt{8})/2\sqrt{8}}{1 - (3 + \sqrt{8})x} - \frac{(3 - \sqrt{8})/2\sqrt{8}}{1 - (3 - \sqrt{8})x}$

and from there, expanding the preceding line in geometric series, we derive a closed form for the $m_k$ :

$\displaystyle m_k = \frac1{2\sqrt{8}}((3 + \sqrt{8})^k - (3 - \sqrt{8})^k)$

Nice! If you prefer, this is just the integer part of $\displaystyle \frac1{2\sqrt{8}}(3 + \sqrt{8})^k$ .

So, the $k^{th}$ triangular square is

$\displaystyle \frac1{32}((3 + \sqrt{8})^{2k} + (3 - \sqrt{8})^{2k} - 2).$

Sweet.

Having gone through this analysis, the same method can be used to determine those squares which are pentagonal (the first few pentagonal numbers are $1, 1+4, 1+4+7, 1+4+7+10, \ldots$ ). I’ll let readers work this out if they like; suffice it to say that the $k^{th}$ square which is also pentagonal is the square of

$\displaystyle \frac1{2\sqrt{24}}((5 + \sqrt{24})^{2k-1} - (5 - \sqrt{24})^{2k-1}).$

And that’s about as far as I got with this. After trying a few numerical forays with a hand-held calculator, my gut feeling is that I’d be amazed if there were any triangular-square-pentagonals past $m = 1$ . But can anyone clinch the case?

[Edit: I’ve corrected the exponents in the last displayed line, from $k$ to $2k-1$ .]

Rational Tangles

August 26, 2008 in Math Topics | Tags: continued fractions | by Todd Trimble | 1 comment

In my post, I made a comment in passing that continued fractions have applications to knot theory. Now A Neighborhood of Infinity has a series of posts on the very topic I had in mind, namely the theory of rational tangles. Much of the theory is due to the great John Horton Conway.

Continued fraction for e

August 4, 2008 in Exposition | Tags: chaos, continued fractions | by Todd Trimble | 28 comments

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 $e = 2.7182818...$ .

[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 $\sqrt{2}$ is 1, 2, 2, 2, … — this means

$\sqrt{2} = 1 + 1/(2 + 1/(2 + 1/(2 + ...))),$

giving the continued fraction representation for $\sqrt{2}$ . Ignoring questions of convergence, this equation should be “obvious”, because it says that the continued fraction you get for $\sqrt{2} - 1$ equals the reciprocal of the continued fraction for $\sqrt{2} + 1$ .

Before launching in on $e$ , 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:

$37/14 = \mathbf{2} + 1/(\mathbf{1} + 1/(\mathbf{1} + 1/(\mathbf{1} + 1/\mathbf{4})))$

duplicate the successive quotients one gets by using the division algorithm to compute $\mbox{gcd}(37, 14)$ :

$37 = \mathbf{2} \cdot 14 + 9$

$14 = \mathbf{1} \cdot 9 + 5$

$9 = \mathbf{1} \cdot 5 + 4$

$5 = \mathbf{1} \cdot 4 + 1$

$4 = \mathbf{4} \cdot 1 + 0$

A number has an infinite continued fraction if and only if it is irrational. Let $I$ denote the space of irrationals between 0 and 1 (as a subspace of $\mathbb{R}$ ). The continued fraction representation (mapping an irrational $x \in I$ to the corresponding infinite sequence of integer parts $a_1, a_2 \ldots$ in its continued fraction representation $x = \left[0, a_1, a_2, \ldots \right]$ ) gives a homeomorphism $I \to \mathbb{N}^{\mathbb{N}},$ where $\mathbb{N}^{\mathbb{N}}$ carries a topology as product of countably many copies of the discrete space $\mathbb{N}$ .

In particular, the shift map $\displaystyle \sigma: \mathbb{N}^{\mathbb{N}} \to \mathbb{N}^{\mathbb{N}}$ , defined by $(\sigma(f))(n) = f(n+1)$ , corresponds to the map $\tau: I \to I$ defined by $\tau(x) = 1/x \pmod 1$ . The behavior of $\tau$ is a paragon, an exemplary model, of chaos:

There is a dense set of periodic points of $\tau$ . These are quadratic surds like $\sqrt{2} - 1$ : elements of $I$ that are fixed points of fractional linear transformations $\displaystyle x \mapsto \frac{ax + b}{cx + d}$ (for integral $a, b, c, d$ and $|ad - bc| = 1$ ).
The transformation $\tau$ 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 $\displaystyle \frac{\sqrt{5} - 1}{2}$ , and hit it with $\tau$ 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 $\displaystyle \mu(E) := \int_E \frac1{1 + x} dx$ on $I$ , where $\mu(I) = \log 2$ . It may be shown that $\tau: I \to I$ is a measure-preserving transformation; much more significantly, $\tau$ is an ergodic transformation on the measure space. It then follows from Birkhoff’s ergodicity theorem that whenever $f: I \to \mathbb{R}$ is integrable, the time averages $\displaystyle \frac1{n} \sum_{k=0}^{n-1} f(\tau^k(x))$ approach the space average $\displaystyle \frac1{\log 2}\int_I f(u) \frac{du}{1 + u}$ for almost all $x \in I$ . Applying this fact to $f([0, a_1, a_2, \ldots]) = \log(a_1)$ , it follows that for almost all irrationals $x \in I$ , the geometric mean of the integer parts $a_1, a_2, \ldots a_n$ approaches a constant, Khinchin’s constant $K = 2.685452...$ . A fantastic theorem!

Anyway, I digress. You are probably waiting to hear about the continued fraction representation of $e$ , which is $\left[2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, \ldots \right]$ :

$e = 2 + 1/(1 + 1/(2 + 1/(1 + 1/(1 + 1/(4 + \ldots)))))$

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,

$e = \left[1, 0, 1, 1, 2, 1, 1, 4, 1, 1, 6, 1, \ldots \right],$

involving triads $1, 2n, 1$ , where $n = 0, 1, 2, \ldots$ .

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 $e$ .

PROOF 1 (sketch)

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

$\displaystyle \tanh(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}},$

related by the equation $\tan(ix) = i\tanh(x)$ . These functions crop up a lot in his investigations. For example, he knew that their Taylor expansions are connected with Bernoulli numbers, e.g.,

$\displaystyle \tanh(x) = \sum_{n \geq 1} \frac{B_{2n}4^n (4^n - 1)}{(2n)!} x^{2n-1}.$

The Taylor coefficients $T_n = E_{2n-1}$ where $\displaystyle \tan(x) = \sum_{n \geq 1} \frac{E_{2n-1} x^{2n-1}}{(2n-1)!}$ 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 $S_n$ , the Taylor coefficients of the secant function. Putting $E_{2n} = S_n$ , the secant and tangent numbers $E_n$ together are called Euler numbers, and enjoy some interesting combinatorics: $E_n$ counts the number of “zig-zag permutations” $k \mapsto a_k$ of $\{1, 2, \ldots, n\}$ , where $a_1 > a_2 < a_3 > \ldots$ . 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 $E_n$ in terms the generating function $\sec(x) + \tan(x)$ , over here.

Euler also discovered a lovely continued fraction representation,

$\displaystyle \tanh(x) = 1/(x^{-1} + 1/(3x^{-1} + 1/(5x^{-1} + \ldots ))),$

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 $x > 0$ , where $0 < \tanh(x) < 1$ . Thus the integer part is 0; subtract the integer part and take the reciprocal, and see what happens.

The MacLaurin series for $\tanh(x)$ is $x - x^3/3 + \ldots = x(1 - x^2/3 + \ldots)$ ; its reciprocal has a pole at 0 of residue 1, so

$\displaystyle \frac1{\tanh(x)} - \frac1{x} = f_1(x)$

gives a function $f_1(x) = x/3 + \ldots$ which is odd and analytic near 0. Now repeat: reciprocating $f_1(x)$ , we get a simple pole at 0 of residue 3, and

$\displaystyle \frac1{f_1(x)} - \frac{3}{x} = f_2(x)$

gives a function $f_2(x)$ which is odd and analytic near 0, and one may check by hand that its MacLaurin series begins as $x/5 + \ldots$ .

The pattern continues by a simple induction. Recursively define (for $x > 0$ )

$\displaystyle f_{n+1}(x) = \frac1{f_n(x)} - (2n+1)x^{-1}$

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

$\displaystyle \tanh(x) = 1/(x^{-1} + 1/(3x^{-1} + \ldots 1/((2n-1)x^{-1} + f_n(x)) \ldots ))$

Indeed, assuming the fact that $f_n(x)$ is uniformly bounded over $n$ , these expressions converge as $n \to \infty$ , so that the continued fraction expression for $\tanh(x)$ is correct.

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

$\displaystyle f_{n}'(x) = 1 - f_n(x)^2 - 2n x^{-1}f_n(x).$

Proof: By induction. In the case $n = 0$ , we have that $f_0(x) = \tanh(x)$ is analytic and

$f_{0}'(x) = 1/\cosh^2(x) = 1 - f_{0}^2(x).$

Assuming the conditions hold when $n = k$ , and writing

$f_k(x) = a_{k1}x + a_{k3}x^3 + \ldots$

we easily calculate from the differential equation that $a_{k1} = 1/(2k+1)$ . It follows that

$\displaystyle f_{k+1}(x) := \frac1{f_k(x)} - (2k+1)x^{-1}$

is indeed analytic in a neighborhood of 0. The verification of the differential equation (as inductive step) for the case $n = k+1$ is routine and left to the reader. $\Box$

Remark: The proof that the continued fraction above indeed converges to $\tanh(x)$ 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 $x$ in the range $(-\pi/2, \pi/2)$ , he gets a uniform bound $|f_n(x)| \leq \tan|x|$ for all $n$ , and notes that as a result convergence of the continued fraction is then easy to prove for such $x$ (good enough for us, as we’ll be taking $x = 1/2$ ). He goes on to say, somewhat telegraphically for my taste, “Careful study of this argument reveals that the power series for $f_n(z)$ actually converges for $|z| < \pi \sqrt{2n+1}/2$ ; therefore the singularities of $f_n(z)$ get farther and farther away from the origin as $n$ grows, and the continued fraction actually represents $\tanh(z)$ throughout the complex plane.” [Emphasis his] Hmm…

Assuming the continued fraction representation for $\tanh(x)$ , let’s tackle $e$ . From the continued fraction we get for instance

$\displaystyle \tanh(1/2) = \frac{e^{1/2} - e^{-1/2}}{e^{1/2} + e^{-1/2}} = 1/(2 + 1/(6 + 1/(10 + \ldots)))$

Taking reciprocals and manipulating,

$\displaystyle 1 + \frac{2}{e - 1} = 2 + 1/(6 + 1/(10 + 1/(14 + \ldots ))).$

Theorem 1: $e-1 = \left[ 1, 1, 2, 1, 1, 4, 1, 1, 6, \ldots \right]$ .

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

$2\left[ 0, 1, 1, 2, 1, 1, 4, 1, 1, 6, \ldots \right] = \left[ 1, 6, 10, 14, \ldots \right].$

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: $2\left[ 0, 2a + 1, b, c, \ldots \right] = \left[ 0, a, 1, 1 + 2\left[ 0, b-1, c, \ldots \right] \right]$ , and

$2\left[0, 2a, b, c, \ldots \right] = \left[ 0, a, 2\left[ b, c, \ldots \right] \right] .$

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

$2\left[ 0, 1, 1, 2, 1, 1, 4, \ldots \right] = \left[ 0, 0, 1, 1 + 2\left[ 0, 0, 2, 1, 1, 4\ldots \right] \right]$

$= \left[ 1, 1 + 2\left[ 2, 1, 1, 4, \ldots \right] \right]$

$= \left[ 1, 1 + 4 + 2\left[ 0, 1, 1, 4, \ldots \right] \right]$

$= \left[ 1, 5 + \left[ 0, 0, 1, 1 + 2\left[ 0, 0, 4, \ldots \right] \right] \right]$

$= \left[ 1, 6 + \left[ 0, 1 + 2\left[ 4, 1, 1, 6, \ldots \right] \right] \right]$

$= \left[ 1, 6, 1 + 2\left[ 4, 1, 1, 6, \ldots \right] \right]$

$= \left[ 1, 6, 1 + 8 + 2\left[ 0, 1, 1, 6, \ldots \right] \right]$

and so on. Continuing this procedure, we get $\left[ 1, 6, 10, 14, \ldots \right]$ , which finishes the proof of theorem 1. $\Box$

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 $\displaystyle \frac{p_n}{q_n} = \left[ a_0, a_1, \ldots, a_n \right]$ provide “best fits” to a given real number $x = \left[ a_0, a_1, \ldots \right]$ . (By “best fit”, I mean a sample theorem like: among all rational numbers whose denominator is bounded above in magnitude by $q_n$ , the approximant $\displaystyle \frac{p_n}{q_n}$ comes closest to $x$ .)

Definition: Let $f$ be a function analytic in a neighborhood of 0. The Padé approximant to $f$ of order $(m, n)$ , denoted $r_{m, n}(x)$ , is the (unique) rational function $\displaystyle \frac{p(x)}{q(x)}$ such that $\mbox{deg}(p) = m$ , $\mbox{deg}(q) = n$ , and the MacLaurin coefficients of $r_{m, n}$ agree with those of $f$ up to degree $m + n$ . $\Box$

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

$\displaystyle \frac{q(x)f(x) - p(x)}{x^{m+n+1}}$

is analytic around 0. Here, we will be interested in Padé approximants to $f(x) = e^x$ .

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 $r$ be a polynomial of degree $k$ . Then there are polynomials $p, q$ of degree at most $k$ such that

$\displaystyle \int_{0}^1 r(t)e^{xt} dt = \frac{q(x)e^x - p(x)}{x^{k+1}}$

Explicitly,

$p(x) = r(0)x^k - r'(0)x^{k-1} + r''(0)x^{k-2} - \ldots$

$q(x) = r(1)x^k - r'(1)x^{k-1} + r''(1)x^{k-2} - \ldots$

Proof: Integration by parts yields

$\displaystyle \int_{0}^1 r(t)e^{xt} dt = \frac{r(1)e^x - r(0)}{x} - \frac1{x} \int_{0}^1 r'(t)e^{xt} dt$

and the general result follows by induction. $\Box$

It is clear that the integral of proposition 1 defines a function analytic in $x$ . Taking $k = m + n$ , this means we can read off the Padé approximant $r_{m, n}(x) = p(x)/q(x)$ to $e^x$ from the formulas for $p, q$ in proposition 1, provided that the polynomial $r(t)$ [of degree $m + n$ ] is chosen so that $\mbox{deg}(p) = m, \mbox{deg}(q) = n$ . Looking at these formulas, all we have to do is choose $r$ to have a zero of order $n$ at $t = 0$ , and a zero of order $m$ at $t = 1$ . Therefore $r(t) = t^n (t-1)^m$ fits the bill.

Notice also we can adjust $r$ by any constant multiple; the numerator and denominator $p(x), q(x)$ are adjusted by the same constant multiples, which cancel each other in the Padé approximant $r_{m, n}(x) = p(x)/q(x)$ .

Taking $r(t) = t^n (t-1)^m$ in proposition 1, we then infer

$\displaystyle \int_{0}^1 t^n (t-1)^m e^t dt = q(1)e - p(1).$

Notice that this integral is small when $m, n$ are large. This means that $r_{m, n}(1) = p(1)/q(1)$ will be close to $e$ (see the following remark), and it turns out that by choosing $m, n$ appropriately, the values $r_{m, n}(1)$ coincide exactly with rational approximants coming from the continued fraction for $e$ .

Remark: Note that for the choice $r(t) =t^n (t-1)^m$ , the values $p(1), q(1)$ derived from proposition 1 are manifestly integral, and $q(1) \neq 0$ . [In particular, $|q(1)| \geq 1$ , justifying the claim that $|p(1)/q(1) - e|$ is small if $q(1)e - p(1)$ is.] In fact, $p(1), q(1)$ may be much larger than necessary; e.g., they may have a common factor, so that the fraction $p(1)/q(1)$ is unreduced. This ties in with how we adjust $r(t)$ by a constant factor, as in theorem 2 below.

For $n \geq 0$ , let $p_n/q_n$ denote the $n^{th}$ rational approximant arising from the infinite continued fraction

$\left[ a_0, a_1, a_2, \ldots \right] = \left[ 1, 0, 1, 1, 2, 1, 1, 4, 1, \dots \right],$

where $\mbox{gcd}(p_n, q_n) = 1$ . From standard theory of continued fractions, we have the following recursive rule for computing the integers $p_n, q_n$ from the $a_n$ : $p_0 = a_0$ , $q_0 = 1$ , $p_{-1} := 1$ , $q_{-1} := 0$ , and

$p_{n+1} = a_{n+1} p_n + p_{n-1} \qquad q_{n+1} = a_{n+1} q_n + q_{n-1}.$

Explicitly, $a_{3n} = a_{3n+2} = 1$ and $a_{3n+1} = 2n$ , so

$p_{3n} = p_{3n-1} + p_{3n-2} \qquad q_{3n} = q_{3n-1} + q_{3n-2}$
$p_{3n+1} = 2n p_{3n} + p_{3n-1} \qquad q_{3n+1} = 2n q_{3n} + q_{3n-1}$
$p_{3n+2} = p_{3n+1} + p_{3n} \qquad q_{3n+2} = q_{3n+1} + q_{3n}$

[Note: $p_1 = 1$ and $q_1 = 0$ , so $p_1/q_1$ is infinite, but that won’t matter below.]

Theorem 2: Define, for $n \geq 0$ ,

$\displaystyle A_n := \int_{0}^1 \frac{t^n (t-1)^n}{n!} e^t dt$

$\displaystyle B_n := \int_{0}^1 \frac{t^{n+1} (t-1)^n}{n!} e^t dt$

$\displaystyle C_n := \int_{0}^1 \frac{t^n (t-1)^{n+1}}{n!} e^t dt$

Then $A_n = q_{3n}e - p_{3n}$ , $B_n = p_{3n+1} - q_{3n+1}e$ , and $C_n = p_{3n+2} - q_{3n+2}e$ .

Proof: It is easy to see $A_0 = e - 1$ , $B_0 = 1$ , and $C_0 = 2 - e$ . In view of the recursive relations for the $p_n, q_n$ above, it suffices to show

$A_n = -B_{n-1} - C_{n-1}$
$B_n = -2n A_{n-1} + C_{n-1}$
$C_n = B_n - A_n$

The last relation is trivial. The first relation $A_n + B_{n-1} + C_{n-1} = 0$ follows by integrating both sides of the identity

$\displaystyle \frac{t^n (t-1)^n e^t}{n!} + \frac{t^n (t-1)^{n-1} e^t}{(n-1)!} + \frac{t^{n-1} (t-1)^n e^t}{(n-1)!} = \frac{d}{dt} \frac{t^n (t-1)^n e^t}{n!}$

over the interval $\left[ 0, 1 \right]$ . The second relation $B_n + 2n A_{n-1} - C_{n-1} = 0$ follows by integrating both sides of the identity

$\displaystyle \frac{t^{n+1} (t-1)^n e^t}{n!} + 2n\frac{t^{n-1} (t-1)^{n-1} e^t}{(n-1)!} - \frac{t^{n-1} (t-1)^n e^t}{(n-1)!} = \frac{d}{dt} \frac{t^n (t-1)^{n+1} e^t}{n!}$

which we leave to the reader to check. This completes the proof. $\Box$

Theorem 2 immediately implies that

$e = \left[ 1, 0, 1, 1, 2, 1, 1, 4, 1, 1, 6, 1, \ldots \right];$

indeed, the rational approximants $p_k/q_k$ to the right-hand side have the property that $q_k |p_k/q_k - e|$ is one of $|A_n|, |B_n|$ , or $|C_n|$ (for $k = 3n, 3n+1, 3n+2$ respectively), and looking at their integral expressions, these quantities approach 0 very rapidly.

This in turn means, since the denominators $q_k$ grow rapidly with $k$ , that the rational approximants $p_k/q_k$ approach $e$ “insanely” rapidly, and this in itself can be used as the basis of a proof that $e$ 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

$1/(x^{-1} + 1/(3x^{-1} + \ldots + 1/(2n+1)x^{-1} \ldots ))$

is to the function $\tanh(x)$ . It’s something on the order of $\displaystyle \frac{(n!)^2}{(2n)!(2n+1)!}$ (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 $e$ ; 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.]

	Strong equidistribut… on Platonic Solids and Euler…
	m.s.mohamed ansari on The 54th Carnival of Math…
	Convictions ·… on Continued fraction for e
	Wayne J. Mann on Solution to POW-12: A graph co…
	erneststephen on The 54th Carnival of Math…
	anhtraisg on p^q + q^p is prime
	prof dr drd horia or… on My first post
	prof drd horia orasa… on My first post
	prof dr mircea orasa… on Inequality with log
	notedscholar on Self-referential Paradoxes, In…
	prof dr mircea orasa… on Inequality with log
	prof dr mircea orasa… on Inequality with log
	prof dr mircea orasa… on 2010 in review
	kenji on Basic category theory, I
	prof dr mircea orasa… on Solution to POW-10: Another ha…

Tag Archive

Almost a problem of the week

Rational Tangles

Continued fraction for e

Our other blog

Visitors to this blog

Blog Stats

Wikio Ranking

Current Online Readers

Recent Comments

Top Posts

Archives

Categories

Blogroll

chess

Computers and Technology

Elementary Math Problem Solving

Fun, Humor

Higher Mathematics

Math Education

Non-technical

Opinions

People in Computer Science

People in mathematics

Philosophy & Logic

Physics

Politics, News

Sciences

Useful general links

Useful Math Links

Tag Cloud

Admin/Users Login

Pages