Uniformly at Random

Posts Tagged ‘continued fractions

The Khinchin-Levy Theorem

with 4 comments

To me, one of the most surprising results in number theory is the Khinchin-Levy Theorem.  This theorem states that for almost all (in the sense of Lebesgue measure) real numbers \alpha, the denominators q_n of the convergents of the continued fraction expansion of \alpha satisfy

\lim_{n \to \infty} q_n^{1/n} = e^{\pi^2/(12 \log 2)}.

The quantity on the right hand side is the so-called Khinchin-Levy constant.  This result is surprising for several reasons:

  1. Why should the limit even exist?
  2. Why should it have the same value for almost all \alpha?
  3. Why should its value involve the three constants e, \pi, and \log 2?


A proof of the Khinchin-Levy Theorem using probability theory can be found in the book Continued Fractions by Rockett and Szusz; it can also be proved using the Ergodic Theorem.

Written by uncudh

March 8, 2009 at 2:40 am

Posted in math

Tagged with ,

Some more curious continued fractions

leave a comment »

We have previously observed that e has the remarkably regular continued fraction expansion e = [2; 1, 2, 1, 1, 4, 1, 1, 6,\ldots].

Another curious continued fraction is the following:

\sum_{n \geq 1} 2^{-\lfloor 2n/(\sqrt{5}-1) \rfloor} = [0; 2^0, 2^1, 2^1, 2^2, 2^3, 2^5, 2^8, 2^{13}, \ldots],

where the exponents of the 2’s in the continued fraction are the Fibonacci numbers. This unusual continued fraction has been independently rediscovered by several authors. See, for example, Anderson, Brown, and Shiue, Proc. Amer. Math. Soc. 123 (1995), 2005-2009.

Among the most famous continued fractions are the Rogers-Ramanujan continued fractions:

\cfrac{1}{1+\cfrac{e^{-2\pi}}{1+\cfrac{e^{-4\pi}}{1+\cfrac{e^{-6\pi}}{\vdots}}}} = \left( \sqrt{\frac{5+\sqrt{5}}{2}} - \frac{\sqrt{5}+1}{2} \right)e^{2\pi/5}

1-\cfrac{e^{-\pi}}{1+\cfrac{e^{-2\pi}}{1-\cfrac{e^{-3\pi}}{\vdots}}} = \left( \sqrt{\frac{5-\sqrt{5}}{2}} - \frac{\sqrt{5}-1}{2} \right)e^{\pi/5}.

Ramanujan included these formulas in his famous 1913 letter to Hardy. Later, Hardy wrote, “[These formulas] defeated me completely. I had never seen anything in the least like them before. A single look at them is enough to show that they could only be written down by a mathematician of the highest class. They must be true because, if they were not true, no one would have had the imagination to invent them.”

Written by uncudh

November 27, 2008 at 1:50 am

Posted in math

Tagged with ,

The continued fraction expansion of e

leave a comment »

It is a somewhat curious fact (due to Euler) that the continued fraction expansion of e has a very regular pattern:

e = [2; 1, 2, 1, 1, 4, 1, 1, 6, \ldots].

There are many different proofs of this result. The proof given here is classical and elementary. It can be found, for instance, in the book by Rockett and Szusz.

We begin with the power series expansion of e^x:

e^x = \sum_{k=0}^\infty x^k/k!.

If m is a positive integer, then we have

e^{1/m} = \sum_{k=0}^\infty (1/m)^k/k!,

(e^{1/m} + e^{-1/m})/2  = \sum_{k=0}^\infty (1/m)^{2k}/(2k)!,

(e^{1/m} - e^{-1/m})/2  = \sum_{k=0}^\infty (1/m)^{2k+1}/(2k+1)!.

Let us also define

x_n = \sum_{k=0}^\infty \frac{2^n(n+k)!}{k!(2n+2k)!}(1/m)^{2k+n}

for n \geq 0, so that x_0 and x_1 are the series given previously for (e^{1/m} + e^{-1/m})/2 and (e^{1/m} - e^{-1/m})/2, respectively. Our first goal is to show that

x_n - m(2n+1)x_{n+1} = x_{n+2}.

Expanding the lefthand side, we have

\sum_{k=0}^\infty \frac{2^n(n+k)!}{k!(2n+2k)!}(1/m)^{2k+n} - m(2n+1) \sum_{k=0}^\infty \frac{2^{n+1}(n+1+k)!}{k!(2n+2+2k)!}(1/m)^{2k+n+1}

= \sum_{k=0}^\infty \frac{2^n(n+k)!}{k!(2n+2k)!}(1/m)^{2k+n} - \sum_{k=0}^\infty \frac{2^{n+1}(2n+1)(n+1+k)!}{k!(2n+2+2k)!}(1/m)^{2k+n}

= \sum_{k=0}^\infty \frac{2^n(n+k)!(2n+2+2k)(2n+1+2k)}{k!(2n+2+2k)!}(1/m)^{2k+n} - \sum_{k=0}^\infty \frac{2^{n+1}(2n+1)(n+1+k)!}{k!(2n+2+2k)!}(1/m)^{2k+n}

= \sum_{k=0}^\infty \frac{2^{n+1}(n+k)!(n+1+k)(2n+1+2k)}{k!(2n+2+2k)!}(1/m)^{2k+n} - \sum_{k=0}^\infty \frac{2^{n+1}(2n+1)(n+1+k)!}{k!(2n+2+2k)!}(1/m)^{2k+n}

= \sum_{k=0}^\infty \frac{2^{n+1}(n+1+k)!(2n+1+2k)}{k!(2n+2+2k)!}(1/m)^{2k+n} - \sum_{k=0}^\infty \frac{2^{n+1}(2n+1)(n+1+k)!}{k!(2n+2+2k)!}(1/m)^{2k+n}

= \sum_{k=0}^\infty \frac{2^{n+1}(n+1+k)![(2n+1+2k)-(2n+1)]}{k!(2n+2+2k)!}(1/m)^{2k+n}

= \sum_{k=0}^\infty \frac{2^{n+1}(n+1+k)!(2k)}{k!(2n+2+2k)!}(1/m)^{2k+n}

= \sum_{k=1}^\infty \frac{2^{n+2}(n+1+k)!k}{k!(2n+2+2k)!}(1/m)^{2k+n}

= \sum_{k=1}^\infty \frac{2^{n+2}((n+2)+(k-1))!}{(k-1)!(2(n+2)+2(k-1))!}(1/m)^{2(k-1)+(n+2)}

= \sum_{k=0}^\infty \frac{2^{n+2}((n+2)+k)!}{k!(2(n+2)+2k)!}(1/m)^{2k+(n+2)}

= x_{n+2}

as required. Now let y_n = x_n/x_{n+1} for n \geq 0. We thus have y_0 = (e^{2/m}+1)/(e^{2/m}-1), and furthermore, we have

y_n = (m(2n+1)x_{n+1} + x_{n+2})/x_{n+1} = m(2n+1) + x_{n+2}/x_{n+1} = m(2n+1) + 1/y_{n+1}.

It follows then that [m; 3m, 5m, \ldots] is the continued fraction expansion of (e^{2/m}+1)/(e^{2/m}-1), and in particular, for m=2, [2; 6, 10, \ldots] is the continued fraction expansion of (e+1)/(e-1).

Recall that if p_n/q_n is the n-th convergent to the continued fraction [a_0; a_1, a_2, \ldots], the following hold: p_{-1} = 1, p_0 = a_0, q_{-1} = 0, q_0 = 1, p_{n+1} = a_{n+1}p_n + p_{n-1}, and q_{n+1} = a_{n+1}q_n + q_{n-1}, for n \geq 0. Thus, if p_n/q_n is the the n-th convergent of [2; 6, 10, \ldots], we have p_{n+1} = 2(2n+1)p_n + p_{n-1}, and q_{n+1} = 2(2n+1)q_n + q_{n-1}.

Let us now recall the claimed expansion e = [2; 1, 2, 1, 1, 4, 1, 1, 6, \ldots]. That is, e = [a_0; a_1, a_2, \ldots], where a_0 = 2, a_1 = 1, a_{3n-1} = 2n, and a_{3n} = a_{3n+1} = 1, for n \geq 1. Letting r_n/s_n denote the convergents to [2; 1, 2, 1, 1, 4, 1, 1, 6, \ldots], we have

r_{3n+1} = r_{3n} + r_{3n-1} = r_{3n-1} + r_{3n-2} + r_{3n-1}

= 2r_{3n-1} + r_{3n-2} = 2(2nr_{3n-2} + r_{3n-3}) + r_{3n-2}

= (2(2n)+1)r_{3n-2} + r_{3n-3} + (r_{3n-4} + r_{3n-5})

= (2(2n)+1)r_{3n-2} + (r_{3n-3} + r_{3n-4}) + r_{3n-5}

= (2(2n)+1)r_{3n-2} + r_{3n-2} + r_{3n-5}

= 2(2n+1)r_{3n-2} + r_{3n-5}

= 2(2n+1)r_{3(n-1)+1} + r_{3(n-2)+1},

for n \geq 2. Similarly, we can show that s_{3n+1} = 2(2n+1)s_{3(n-1)+1} + s_{3(n-2)+1}. However, observe that r_{3n+1} and s_{3n+1} satisfy the same recurrence as p_n and q_n.  Furthermore, when n=0 we can check that r_1 = p_0 + q_0 and s_1 = p_0 - q_0; and similarly, when n=1, we have r_4 = p_1 + q_1 and s_4 = p_1 - q_1. It follows that r_{3n+1} = p_n + q_n and s_{3n+1} = p_n - q_n for n \geq 0.

We can complete the proof if we can show that r_{3n+1}/s_{3n+1} converges to e as n tends to infinity. Note that

r_{3n+1}/s_{3n+1} = (p_n + q_n)/(p_n - q_n) = (p_n/q_n + 1)/(p_n/q_n - 1).

However, we have previously noted that p_n/q_n converges to (e+1)/(e-1), so r_{3n+1}/s_{3n+1} converges to \frac{(e+1)/(e-1)+1}{(e+1)/(e-1)-1} = e, and the proof is complete.

Written by uncudh

November 19, 2008 at 6:22 pm

Posted in math

Tagged with ,