Derangements and Continued Fractions for e

We show in this post that an elegant continued fraction for ${e}$ can be found using derangement numbers. Recall from last week’s post that we call any permutation of the elements of a set an arrangement. A derangement is an arrangement for which every element is moved from its original position.

The number of arrangements of a set of ${n}$ elements is the factorial ${n!}$ and the number of derangements is the subfactorial ${!n}$ . The connection between ${!n}$ and ${n!}$ is established using the inclusion-exclusion principle, and we have

$\displaystyle \frac{!n}{n!} \rightarrow \frac{1}{e} \qquad\mbox{as}\qquad n \rightarrow \infty$

In fact, ${!n}$ is the nearest whole number to ${n!/e}$ [see previous post].

Continued Fractions and Convergents

The continued fraction expansion of an irrational number ${x}$ is written, in expanded form and concise form, as

$\displaystyle x = a_0 + \cfrac{1}{ a_1 + \cfrac{1}{ a_2 + \cfrac{1}{ a_3 + \ddots } }} = [ a_0 ; a_1 , a_2 , a_3 , \dots ]$

where ${a_n}$ are integers. If ${a_n}$ is positive for ${n \ge 1}$ this is called a simple continued fraction.

The generalized continued fraction expansion is written

$\displaystyle x = b_0 + \cfrac{a_1}{ b_1 + \cfrac{a_2}{ b_2 + \cfrac{a_3}{ b_3 + \ddots } }} = b_0 +\frac{a_1}{b_1+}\,\frac{a_2}{b_2+}\,\frac{a_3}{b_3+}\,\frac{a_4}{b_4+}\,\cdots \,.$

where ${a_n}$ and ${b_n}$ are integers. Truncating the expansion at various points, we obtain the convergents

$\displaystyle r_n = \frac{p_n}{q_n} = b_0 +\frac{a_1}{b_1+}\,\frac{a_2}{b_2+}\,\frac{a _3}{b_3+}\,\frac{a_4}{b_4+}\,\cdots\,\frac{a_n}{b_n}$

where the numerators and denominators, ${p_n}$ and ${q_n}$ , are integers.

We define the starting values

$\displaystyle p_{-1} = 1\,, \qquad q_{-1} = 0\,, \qquad p_0 = b_0\,, \qquad q_0 = 1 \,.$

Then, ${p_{k}}$ and ${q_{k}}$ for ${k\ge 1}$ are given by recurrence relations:

$\displaystyle p_{k} = b_{k} p_{k-1} + a_{k} p_{k-2} \,, \qquad q_{k} = b_{k} q_{k-1} + a_{k} q_{k-2} \,, \ \ \ \ \ (1)$

which may be proved by induction.

This process can be inverted: given a sequence of numerators ${p_n}$ and denominators ${q_n}$ (or just their ratios, the convergents ${r_n = p_n/q_n}$ ), we can solve (1) for ${a_n}$ and ${b_n}$ :

$\displaystyle a_n = \frac{p_{n-1}q_{n} - p_{ n}q_{n-1}} {p_{n-1}q_{n-2} - p_{n-2}q_{n-1}} \,, \qquad b_n = \frac{p_{n}q_{n-2} - p_{n-2}q_{n}} {p_{n-1}q_{n-2} - p_{n-2}q_{n-1}} \ \ \ \ \ (2)$

together with the starting values ${b_0=p_0}$ , ${a_1 = (p_1-b_0q_1)}$ and ${b_1=q_1}$ .

Continued Fractions for ${e}$

Euler’s number is usually defined as the limit ${ e = \lim_{n\rightarrow\infty}(1+1/n)^n}$ . This is the limit of the sequence

$\displaystyle \left\{ \frac{2^1}{1^1}, \frac{3^2}{2^2}, \frac{4^3}{3^3}, \dots ,\frac{(n+1)^n}{n ^n}, \dots \right\}$

The terms may be regarded as the convergents of a continued fraction,

$\displaystyle r_n = \frac{p_n}{q_n} \qquad\mbox{where}\qquad p_n = (n+1)^n \quad\mbox{and}\quad q_n = n^n \,.$

We can generate a continued fraction by using (2). It begins as

$\displaystyle 1 +\frac{1}{1-}\,\frac{1}{5-}\,\frac{13}{10-}\,\frac{491}{196-}\, \frac{487903}{9952-}\,\frac{2384329879}{958144-}\, \cdots \,. \ \ \ \ \ (3)$

The error of this expansion ( ${\log_{10}[r_n-e]}$ ) as a function of truncation is shown in the figure below (dashed black line). It is clear that the convergence is very slow.

Euler made extensive studies of continued fractions. For example, his 50-page paper, Observations on continued fractions (Euler, 1750), contains numerous original results. One of his best-known expansions is

$\displaystyle e = [2; 1,2,1,1,4,1,1,6,1,1,8,\dots] \ \ \ \ \ (4)$

The error of Euler’s expansion is shown in the figure (dotted red line). It converges much faster than (3). There is a clear signal of period 3, consistent with the recurring pattern ${(1, 1, n)}$ in (4).

Logarithm of the error $\log_{10}|r_n - e |$ in the continued fraction expansions for $e$. Dashed black line: $r_n=(1+1/n)^n$ , Eq. (3) . Dotted red line: Convergents of Euler’s expansion (4). Solid blue line: $r_n=(n+1)!/!(n+1)$ , Eq. (5).

Continued fraction from derangement numbers

A beautiful continued fraction emerges from the relationship between arrangements and derangements. We saw above that

$\displaystyle \left[ \frac{\mbox{Arrangements of n elements}}{\mbox{Derangements of n elements}} \right] = \frac{n!}{!n} \to e$

If we define the numerators and denominators of convergents to be

$\displaystyle p_n = n! \quad\mbox{and}\quad q_n = \,!n \,,$

we can solve for the factors ${a_n}$ and ${b_n}$ . The starting values ${p_0=1, p_1=1, q_0=1, q_1=0}$ yield ${a_0=0, b_0=1, a_1=1, b_1=0}$ . Then (2) may be solved to yield ${a_n = b_n = (n-1)}$ for ${n\ge 2}$ . Thus we get the expansion

$\displaystyle e = 1 +\frac{1}{0+}\,\frac{1}{1+}\,\frac{2}{2+}\,\frac{3}{3+}\,\frac{4}{4+}\,\cdots \,.$

A small adjustment enables us to write this in the elegant form

$\displaystyle e = 2 +\frac{2}{2+}\,\frac{3}{3+}\,\frac{4}{4+}\,\frac{5}{5+}\,\frac{6}{6+}\,\cdots \,. \ \ \ \ \ (5)$

The error of (5) is shown in the figure above (solid blue line). Convergence is more rapid than for the other two expansions.

For a more detailed discussion, and connection with The Ramanujan Machine, see Lynch (2020).

References

${\bullet}$ Euler, L., 1750: De fractionibus continuis observationes. Commentarii academiae scientiarum Petropolitanae, 11, 32–81. Reprinted in Opera Omnia, Series 1, 14, 291–349. Translation by Alexander Aycock: Observations on continued fractions. PDF .

${\bullet}$ Lynch, Peter 2020: Derangements and Continued Fractions for e. eprint on arXiv .

* * * * *

That’s Maths II: A Ton of Wonders

by Peter Lynch has just appeared.
Full details and links to suppliers at
http://logicpress.ie/2020-3/

* * * * *

ThatsMaths