View source for Continued fraction

{{MSC|}}
{{TEX|done}}

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
{{Cite|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,
{{Cite|Ma}} and
{{Cite|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
{{Cite|Bu}},
{{Cite|Ve}},
{{Cite|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
{{Cite|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
{{Cite|Bu}} and
{{Cite|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.,
{{Cite|Sz}}).

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


====References====
{|
|-
|valign="top"|{{Ref|Bo}}||valign="top"|  D.I. Bodnap,   "Convergent continued fractions", Kiev  (1986)  (In Russian)   
|-
|valign="top"|{{Ref|Br}}||valign="top"|  A.J. Brentjes,   "Multidimensional continued fractions", CWI, Amsterdam  (1981)  {{MR|0638474}}  
|-
|valign="top"|{{Ref|Bu}}||valign="top"|  A.A. Bukhshtab,   "Number theory", Moscow  (1966)  (In Russian)   
|-
|valign="top"|{{Ref|HaWr}}||valign="top"|  G.H. Hardy,   E.M. Wright,   "An introduction to the theory of numbers", Oxford Univ. Press  (1959)  {{MR|2568169}} {{MR|2445243}} {{MR|0568909}} {{MR|0067125}} {{MR|1561815}}  
|-
|valign="top"|{{Ref|He}}||valign="top"|  P. Henrici,   "Applied and computational complex analysis", '''2''', Wiley  (1977)  {{MR|0453984}}  
|-
|valign="top"|{{Ref|JoTh}}||valign="top"|  W.B. Jones,   W.J. Thron,   "Continued fractions, analytic theory and applications", Addison-Wesley  (1980)   
|-
|valign="top"|{{Ref|JoThWa}}||valign="top"|  W.B. Jones (ed.)  W.J. Thron (ed.)  E.H. Waadeland (ed.), ''Analytic theory of continued fractions'', ''Lect. notes in math.'', '''932''', Springer  (1982)  {{MR|0690450}}  
|-
|valign="top"|{{Ref|Kh}}||valign="top"|  A.Ya. [A.Ya. Khinchin] Khintchine,   "Kettenbrüche", Teubner  (1956)  (Translated from Russian)  {{MR|1544727}} {{MR|1512207}} {{MR|1544632}}  
|-
|valign="top"|{{Ref|Kh2}}||valign="top"|  A.N. Khovanskii,   "Application of continued fractions and their generalizations to problems in approximation theory", Moscow  (1966)  (In Russian)  {{MR|1533406}} {{MR|0156126}}  
|-
|valign="top"|{{Ref|Kr}}||valign="top"|  C. Kraaikamp,   "The distribution of some sequences connected with the nearest integer continued fraction"  ''Indag. Math.'', '''49'''  (1987)  pp. 177–191  {{MR|0898162}}  
|-
|valign="top"|{{Ref|Ma}}||valign="top"|  A.A. Markov,   "Selected works", Moscow-Leningrad  (1948)  (In Russian)  {{MR|2086689}} {{MR|2086688}} {{MR|0050525}}  
|-
|valign="top"|{{Ref|Pe}}||valign="top"|  O. Perron,   "Die Lehre von den Kettenbrüchen", '''1–2''', Teubner  (1954–1957)  {{MR|0064172}}  
|-
|valign="top"|{{Ref|Sk}}||valign="top"|  V.Ya. Skorobogatko,   "The theory of convergent continued fractions and its applications in numerical mathematics", Moscow  (1983)  (In Russian)   
|-
|valign="top"|{{Ref|Sz}}||valign="top"|  G. Szekeres,   "Multidimensional continued fractions"  ''Ann. Univ. Sci. Sec. Math.'', '''13'''  (1970)  pp. 113–140  {{MR|0313198}}  
|-
|valign="top"|{{Ref|Th}}||valign="top"|  W.J. Thron (ed.), ''Analytic theory of continued fractions II'', ''Lect. notes in math.'', '''1199''', Springer  (1986)  {{MR|0870239}}  
|-
|valign="top"|{{Ref|Ve}}||valign="top"|  B.A. Venkov,   "Elementary number theory", Wolters-Noordhoff  (1970)  (Translated from Russian)  {{MR|0265267}}  
|-
|valign="top"|{{Ref|Wa}}||valign="top"|  H.S. Wall,   "Analytic theory of continued fractions", Chelsea  (1973)  {{MR|0025596}} {{MR|0008102}}  
|-
|valign="top"|{{Ref|X}}||valign="top"|, ''Ueber die Kwadratur des Kreises''  (1936)   
|}