Continued fraction

A continued fraction is an expression of the form

$$a_0+{b_1|\over |a_1}+\cdots+{b_n|\over |a_n}+\cdots,\label{1}$$ where

$$\def\o{\omega}\{a_n\}_{n=0}^\o\label{2}$$ and

$$\{b_n\}_{n=1}^\o\label{3}$$ are finite or infinite sequences of complex numbers. Instead of the expression (1) one also uses the notation

$$a_0 + \cfrac{b_1}{a_1 + \cfrac{b_2}{{\kern-10pt\raise4pt\ddots} {\strut\atop{\displaystyle a_{n-1} + \cfrac{b_n}{a_n+ {\atop\displaystyle\ddots}}}}}}$$ The continued fraction of the sequence (2) is defined as the expression

$$a_0+{1|\over |a_1}+\cdots+{1|\over |a_n}+\cdots.$$ For every continued fraction (1) the recurrence equations

$$P_n = a_n P_{n-1}+b_n P_{n-2},$$

$$Q_n = a_n Q_{n-1}+b_n Q_{n-2},$$ with the initial conditions

$$b_0 = 1,\quad P_{-2} = 0,\quad P_{-1} = 1,\quad Q_{-2} = 1,\quad Q_{-1} = 0,$$ determine two sequences $\{P_n\}_{n=0}^\o$ and $\{Q_n\}_{n=0}^\o$ of complex numbers. As a rule, it is assumed that the sequences (2) and (3) are such that $Q_n\ne 0$ for all $n$, $0\le n \le \o+1$. The fraction $\def\d{\delta}\d = P_n/Q_n$ is called the $n$-th convergent of the continued fraction (1). Here

$$\d_0 = a_0,\quad \d_1 = a_0+{b_1\over a_1} \quad \d_2 = a_0+{b_1\over {a_1+{b_2\over a_2}}}, \cdots,$$ moreover,

$$\d_n-\d_{n-1} = {(-1)^{n-1}b_1\cdots b_n\over Q_n Q_{n-1}}.$$ It is convenient to denote the $n$-th convergent of the continued fraction of the sequence (2) by

$$[a_0;a_1,\dots,a_n].$$ These convergents satisfy the following equalities:

$$[a_n;\dots,a_1] = {Q_n\over Q_{n-1}}\quad \text{ for } n\ge 1,$$

$$[a_n;\dots,a_0] = {P_n\over P_{n-1}}\quad \text{ for } a_0\ne 0 \text{ and } n\ge 0.$$ If $\o = \infty$ and the sequence of convergents of (1) converges to some limit $l$, then the continued fraction (1) is called convergent and the number $l$ is its value. If $\o < \infty$, that is, the continued fraction is finite, then its value is defined as the last of its convergents.

If all terms of the sequences (2) and (3), except possibly $a_0$, are positive real numbers, and if $a_0$ is real, then the sequence $\d_0,\d_2,\d_4,\dots$ of convergents of even order of (1) increases, and the sequence $\d_1,\d_3,\d_5,\dots$ of convergents of odd order decreases. Here a convergent of even order is less than the corresponding convergent of odd order (see [Kh2]).

If $\def\a{\alpha}\a_0,\a_1, \dots $ is the sequence of complex numbers for which

$$\a_0 = a_0+{b_1\over\a_1},\quad \a_1 = a_1+{b_1\over \a_2},\; \dots,$$ then the expression (1) is called an expansion of the number $\a_0$ in a continued fraction. Not every continued fraction converges, and the value of a continued fraction is not always equal to the number from which it is expanded. There are a number of criteria for the convergence of continued fractions (see, for example, [Ma] and [Kh2]):

1) Suppose that $\o=\infty$, that all terms of the sequences (2) and (3) are real numbers, and that $a_n > 0$ for all natural numbers $n$ from some term onwards. If $a_n-|b_n| \ge 1$ for such $n$, then the continued fraction (1) converges.

2) Suppose that $\o=\infty$ and that all terms of the sequence (2) beginning with $a_1$ are positive. Then the continued fraction of the sequence (2) converges if and only if the series $\sum_{n=0}^\infty a_n$ diverges (Seidel's theorem).

The continued fraction of a sequence (2) is called regular if all its terms (except possibly $a_0$) are natural numbers, $a_0$ is an integer and $a_\o\ge 2$ for $1\le\o<\infty$. For every real number $r$ there exists a unique regular continued fraction with value $r$. This fraction is finite if and only if $r$ is rational (see [Bu], [Ve], [Kh]). An algorithm for the expansion of a real number $r$ in a regular continued fraction is defined by the following relations

$$ \begin{array}{lll} a_0=[r], & \a_1={1\over r-a_0} & \text{ if } a_0 \ne r,\\ a_1=[\a_1], & \a_2={1\over \a_1-a_1} & \text{ if } a_1\ne \a_1,\\ a_2=[\a_2], &\dots & \end{array}\label{4}$$ where $[x]$ denotes the integral part of $x$.

The numbers $a_n$ and $\a_n$ defined by (4) are called, respectively, the complete and incomplete quotients of order $n$ of the expansion of $r$ in a continued fraction.

Around 1768 J. Lambert found the expansion of $\tan x$ in a continued fraction:

$${1|\over |1/x} - {1|\over |3/x} -\cdots - {1|\over |(2n+1)/x} - \cdots.$$ Under the assumption that this continued fraction converges, A. Legendre proved that its value for rational values of $x$ is irrational. It should be mentioned that in this way he proved the irrationality of the number $\pi$ (see [X]).

L. Euler found in 1737 that

$${1\over 2}(e-1)={1|\over|1} + {1|\over|6} + {1|\over|10} + {1|\over|14} +\cdots.$$ A real number $r$ is an irrational root of a polynomial of degree 2 with integer coefficients if and only of the incomplete quotients of the expansion of $r$ in a continued fraction from some term onwards are repeated periodically (the Euler–Lagrange theorem, see [Bu] and [Kh]). At present (1984) expansions in regular continued fractions of algebraic numbers of degree 3 and higher are not known. The assertion that the incomplete quotients of the expansion of $2^{1/3}$ in a continued fraction are bounded has not been proved.

Regular continued fractions are a very convenient tool for the approximation of real numbers by rational numbers. The following propositions hold:

1) If $\d_n = P_n/Q_n$ and $\d_{n+1} = P_{n+1}/Q_{n+1}$ are neighbouring convergents of the expansion of a number $r$ in a regular continued fraction, then

$$|r-\d_n| \ge |r -\d_{n+1}|$$ and

$$\Big|r-{P_n\over Q_n}\Big| \le {1\over Q_nQ_{n+1}},$$ where in the latter case equality holds only when $r= \d_{n+1}$.

2) For two neighbouring convergents of the expansion of a number $r$ in a regular continued fraction, at least one of them satisfies the inequality:

$$\Big|r-{P_n\over Q_n}\Big| = {1\over 2 Q_n^2},$$ 3) If $a$ and $b$ are integers, $b\ge 1$, if $r$ is a real number, and if

$$\Big|r-{a\over b}\Big| \le {1\over 2 b^2},$$ then $a/b$ is a convergent of the expansion of $r$ in a regular continued fraction.

4) If $\d_n = P_n/Q_n$ is a convergent of the expansion of a number $r$ into a regular continued fraction, then for any integers $a$ and $b$ it follows from $b>0$, $\d_n \ne a/b$ and

$$\Big|r-{a\over b}\Big| \le |r-\d_n|,$$ that $b> Q_n$ (theorem on the best approximation).

The first twenty-five incomplete quotients of the expansion of the number $\pi$ in a regular continued fraction are: 3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1.

The first five convergents of the expansion of $\pi$ in a regular continued fraction are:

$$\d_0 = 3,\; \d_1 = {22\over 7},\; \d_2 = {333\over 116},\; \d_3 = {355 \over 113},\; \d_3 = {103993 \over 33102}.$$ Therefore,

$$\Big|\pi - {22\over 7}\Big| < {1\over742} \text{ and } \Big|\pi -{355\over 113}\Big|< 3.10^{-7}.$$ There exist several generalizations of continued fractions (see, e.g., [Sz]).

Comments

A classical reference on convergence is [Wa]. Together with [JoTh], recent references are [JoThWa],[Th],[Kr]. Some generalizations can be found in [Br],[Sk], [Bo]. Except for [Wa], [HaWr] all references contain extensive lists of references on recent developments and applications in Padé approximation; moment problems (cf. Moment problem); orthogonal polynomials; number theory; and the metrical theory of continued fractions (see also Metric theory of numbers).

References

[Bo]	D.I. Bodnap, "Convergent continued fractions", Kiev (1986) (In Russian)
[Br]	A.J. Brentjes, "Multidimensional continued fractions", CWI, Amsterdam (1981) MR0638474
[Bu]	A.A. Bukhshtab, "Number theory", Moscow (1966) (In Russian)
[HaWr]	G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers", Oxford Univ. Press (1959) MR2568169 MR2445243 MR0568909 MR0067125 MR1561815
[He]	P. Henrici, "Applied and computational complex analysis", 2, Wiley (1977) MR0453984
[JoTh]	W.B. Jones, W.J. Thron, "Continued fractions, analytic theory and applications", Addison-Wesley (1980)
[JoThWa]	W.B. Jones (ed.) W.J. Thron (ed.) E.H. Waadeland (ed.), Analytic theory of continued fractions, Lect. notes in math., 932, Springer (1982) MR0690450
[Kh]	A.Ya. [A.Ya. Khinchin] Khintchine, "Kettenbrüche", Teubner (1956) (Translated from Russian) MR1544727 MR1512207 MR1544632
[Kh2]	A.N. Khovanskii, "Application of continued fractions and their generalizations to problems in approximation theory", Moscow (1966) (In Russian) MR1533406 MR0156126
[Kr]	C. Kraaikamp, "The distribution of some sequences connected with the nearest integer continued fraction" Indag. Math., 49 (1987) pp. 177–191 MR0898162
[Ma]	A.A. Markov, "Selected works", Moscow-Leningrad (1948) (In Russian) MR2086689 MR2086688 MR0050525
[Pe]	O. Perron, "Die Lehre von den Kettenbrüchen", 1–2, Teubner (1954–1957) MR0064172
[Sk]	V.Ya. Skorobogatko, "The theory of convergent continued fractions and its applications in numerical mathematics", Moscow (1983) (In Russian)
[Sz]	G. Szekeres, "Multidimensional continued fractions" Ann. Univ. Sci. Sec. Math., 13 (1970) pp. 113–140 MR0313198
[Th]	W.J. Thron (ed.), Analytic theory of continued fractions II, Lect. notes in math., 1199, Springer (1986) MR0870239
[Ve]	B.A. Venkov, "Elementary number theory", Wolters-Noordhoff (1970) (Translated from Russian) MR0265267
[Wa]	H.S. Wall, "Analytic theory of continued fractions", Chelsea (1973) MR0025596 MR0008102
[X]	, Ueber die Kwadratur des Kreises (1936)