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:

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

Bizarre!

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 continued fractions, number theory

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 continued fractions, number theory

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 continued fractions, number theory