The continued fraction expansion of e

Seth Kleinerman

December 13, 2002

1 Introduction

While working with the transcendental number e, Euler wrote down its continued fraction expansion. He observed a pattern and noted that it seemed to continue, though he did not present a proof of this fact. That he did not suggests that the proof is not entirely obvious.

In the article about e in Eric Weisstein’s World of Mathematics, http://mathworld.wolfram.com/e.html, Weisstein states that the continued fraction “follows immediately by rewriting the series … for e as

e = 1 + 1 + \frac{1}{2}(1 + \frac{1}{3}(1 + \frac{1}{4}(1 + \frac{1}{5}(1 + …)))),

which gives a pretty nested radical result when x is taken to the power of both sides.” One can only presume that he means by this to somehow use the equation

x^{e} = x^{2}\sqrt{x\sqrt[3]{x\sqrt[4]{x\sqrt[5]{x …}}}},

but how this relates in an immediate way to the continued fraction expansion is unclear.

In fact, I have not found very many elementary proofs of the result; the statement appears to be much more well known than its proof. Of course, the continued fraction representation of e is treated in standard texts in the theory of continued fractions, foremost among which is Oskar Perron’s Die Lehre von den Kettenbrüchen (which has gone through several editions since it was published in 1913). However, the proof requires a good amount of background in the text and I was looking for something more elementary; also, I found myself struggling with the German.

The proof I will present draws on a short paper by Henry Cohn, “A proof of the continued fraction expansion of e,” which can be found on his website at http://research.microsoft.com/∼cohn/Papers/e.pdf. I have modified and extended the argument slightly but not the general method. The idea of this proof, according to Cohn, is originally due to Hermite.

2 Preliminaries

If we apply the continued fraction algorithm to e = 2.718281828 …, we have

[a_{0}, a_{1}, a_{2}, …] = [2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, …].

In this paper, we prove that the pattern above persists in the continued fraction expansion of e, that is, we will demonstrate a method of computing this particular aperiodic infinite continued fraction, and show that it converges to e.

First, we’ll write the sequence in a slightly altered form. Instead of writing [2, 1, 2, 1, 1, 4, …], we can start the sequence of coefficients [1, 0, 1, 1, 2, 1, 1, 4, …] to make the pattern the same throughout. Here are the recurrences for the numerators and denominators of the convergents given by this new sequence. Using r_{i} as a stand-in for p_{i} or q_{i}, we have

r_{3n} = r_{3n−1} + r_{3n−2}
r_{3n−1} = r_{3n−2} + r_{3n−3}
r_{3n−2} = 2(n − 1)r_{3n−3} + r_{3n−4}.

Table 1: Convergents

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & ⋯ \\ x_{n} & 1 & 3 & 19 & 193 & 2721 & ⋯ \\ y_{n} & 1 & 1 & 7 & 71 & 1001 & ⋯ \\ x_{n}/y_{n} & 1 & 3 & 2.714 … & 2.71830 … & 2.7182817 … & ⋯ \end{matrix}

Our first goal is to collapse these three recurrences into one recurrence that only makes mention of r_{3n}, r_{3n−3}, and r_{3n−6}. To achieve this, we have a little bit of algebraic manipulation on our hands:

r_{3n} = r_{3n−1} + r_{3n−2}
= (r_{3n−2} + r_{3n−3}) + (2(n − 1)r_{3n−3} + r_{3n−4})
= (4n − 3)r_{3n−3} + 2r_{3n−4}.

This same method of simplification also shows us that

r_{3n−3} = 2r_{3n−7} + (4n − 7)r_{3n−6}.

To get rid of 2r_{3n−4} in the first equation, we make the substitutions

2r_{3n−4} = 2(r_{3n−5} + r_{3n−6})
= 2((2(n − 2)r_{3n−6} + r_{3n−7}) + r_{3n−6})
= (4n − 6)r_{3n−6} + 2r_{3n−7}.

Substituting for 2r_{3n−4} and then 2r_{3n−7}, we finally have the needed collapsed recurrence,

r_{3n} = 2(2n − 1)r_{3n−3} + r_{3n−6}.

3 Two integral sequences

We define the sequences x_{n} = p_{3n}, y_{n} = q_{3n}. Since the 3n-convergents will converge to the same real number that the n-convergents do, x_{n}/y_{n} also converges to the limit of the continued fraction. Each sequence {x_{n}}, {y_{n}} will obey the recurrence relation derived in the previous section (where z_{n} is a stand-in for x_{n} or y_{n}):

z_{n} = 2(2n − 1)z_{n−1} + z_{n−2}, for all n ≥ 2.  (1)

The two sequences can be found in Table 1. (The initial conditions x_{0} = 1, x_{1} = 3, y_{0} = y_{1} = 1 are taken straight from the first few convergents of the original continued fraction.) Notice that since we’re skipping several convergents at each step, the ratio x_{n}/y_{n} converges to e very quickly.

4 A related sequence of integrals

Now, we define a sequence of real numbers T_{0}, T_{1}, T_{2}, … by the following integrals:

T_{n} = ∫_{0}^{1} \frac{t^{n}(t − 1)^{n}}{n!} e^{t}dt.

Below, we compute the first two terms of this sequence explicitly. (When we compute T_{1}, we are doing the integration by parts u = t(t − 1), dv = e^{t}dt. Since the integral runs from 0 to 1, the boundary condition is 0 when evaluated at each of the endpoints. This vanishing will be helpful when we do the integral in the general case.)

T_{0} = ∫_{0}^{1} e^{t}dt = e − 1,
T_{1} = ∫_{0}^{1} t(t − 1)e^{t}dt
= − ∫_{0}^{1}((t − 1) + t)e^{t}dt

= −(t − 1)e^{t}|_{0}^{1} − te^{t}|_{0}^{1} + 2 ∫_{0}^{1} e^{t}dt
= 1 − e + 2(e − 1) = e − 3.

The reason that we defined this series now becomes apparent: T_{0} = y_{0}e − x_{0} and that T_{1} = y_{1}e − x_{1}. In general, it will be true that T_{n} = y_{n}e − x_{n}. We will now prove this fact.

It is clear that if the T_{n} were to satisfy the same recurrence that the x_{i} and y_{i} do, in equation (1), then the above statement holds by induction. (The initial conditions are correct, as needed.) So we simplify T_{n} by integrating by parts twice in succession:

T_{n} = ∫_{0}^{1} \frac{t^{n}(t − 1)^{n}}{n!} e^{t}dt

= − ∫_{0}^{1} \frac{t^{n−1}(t − 1)^{n} + t^{n}(t − 1)^{n−1}}{(n − 1)!} e^{t}dt

= ∫_{0}^{1} (\frac{t^{n−2}(t − 1)^{n}}{(n − 2)!} + n\frac{t^{n−1}(t − 1)^{n−1}}{(n − 1)!} + n\frac{t^{n−1}(t − 1)^{n−1}}{(n − 1)!} + \frac{t^{n}(t − 1)^{n−2}}{(n − 2)!} ) e^{t}dt

= 2nT_{n−1} + ∫_{0}^{1} \frac{t^{n−2}(t − 1)^{n−2}}{n − 2!} (2t^{2} − 2t + 1) e^{t}dt

= 2nT_{n−1} + 2 ∫_{0}^{1} \frac{t^{n−1}(t − 1)^{n−1}}{n − 2!} e^{t}dt + ∫_{0}^{1} \frac{t^{n−2}(t − 1)^{n−2}}{n − 2!} e^{t}dt

= 2nT_{n−1} + 2(n − 1)T_{n−1} + T_{n−2}

= 2(2n − 1)T_{n−1} + T_{n−2},

which is the desired recurrence.

Therefore T_{n} = y_{n}e − x_{n}. To conclude the proof, we consider the limit as n approaches infinity:

lim_{n→∞} ∫_{0}^{1} \frac{t^{n}(t − 1)^{n}}{n!} e^{t}dt = 0,

by inspection, and therefore

lim_{n→∞} \frac{x_{n}}{y_{n}} = lim_{n→∞}(e − \frac{T_{n}}{y_{n}}) = e.

Therefore, the ratio x_{n}/y_{n} approaches e, and the continued fraction expansion [2, 1, 2, 1, 1, 4, 1, 1, …] does in fact converge to e.

5 Extensions

This method of proof can be generalized to confirm the continued fraction expansion of e^{1/k}, which equals [1, (k −1), 1, 1, (3k −1), 1, 1, (5k −1), 1, 1, (7k −1) …] for all k ∈ ℕ. The condensed recurrence relation we derived in the beginning changes slightly, and so does the integral sequence we will consider. We define the new sequence by

T_{n}^{k} = k^{n} ∫_{0}^{1} \frac{(\frac{t}{k})^{n}(\frac{t}{k} − 1)^{n}}{n!} e^{t}dt for n ∈ ℕ.

But, exactly as before, the integrals produce the 3n-convergents:

T_{n}^{k} = q_{3n}e^{1/k} − p_{3n} = y_{n}e^{1/k} − x_{n}.

(We would need to prove this. It is similar to the k = 1 case: we check the initial conditions and that the {T_{n}^{k}}, {x_{n}}, and {y_{n}} sequences all satisfy the same recurrence.) This type of argument confirms the continued fraction expansion for the kth root of e, for all positive integers k.