Namespaces
Variants
Actions

Difference between revisions of "Continued fraction"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m
Line 1: Line 1:
An expression of the form
+
{{MSC|}}
 +
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c0255401.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
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
 
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c0255402.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$\def\o{\omega}\{a_n\}_{n=0}^\o\label{2}$$
 
 
 
and
 
and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c0255403.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$\{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
 
are finite or infinite sequences of complex numbers. Instead of the expression (1) one also uses the notation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c0255404.png" /></td> </tr></table>
+
$$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
 
The continued fraction of the sequence (2) is defined as the expression
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c0255405.png" /></td> </tr></table>
+
$$a_0+{1|\over |a_1}+\cdots+{1|\over |a_n}+\cdots.$$
 
 
 
For every continued fraction (1) the recurrence equations
 
For every continued fraction (1) the recurrence equations
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c0255406.png" /></td> </tr></table>
+
$$P_n = a_n P_{n-1}+b_n P_{n-2},$$
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c0255407.png" /></td> </tr></table>
 
  
 +
$$Q_n = a_n Q_{n-1}+b_n Q_{n-2},$$
 
with the initial conditions
 
with the initial conditions
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c0255408.png" /></td> </tr></table>
+
$$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
determine two sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c0255409.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554010.png" /> of complex numbers. As a rule, it is assumed that the sequences (2) and (3) are such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554011.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554013.png" />. The fraction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554014.png" /> is called the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554015.png" />-th convergent of the continued fraction (1). Here
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554016.png" /></td> </tr></table>
 
  
 +
$$\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,
 
moreover,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554017.png" /></td> </tr></table>
+
$$\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
It is convenient to denote the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554018.png" />-th convergent of the continued fraction of the sequence (2) by
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554019.png" /></td> </tr></table>
 
  
 +
$$[a_0;a_1,\dots,a_n].$$
 
These convergents satisfy the following equalities:
 
These convergents satisfy the following equalities:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554020.png" /></td> </tr></table>
+
$$[a_n;\dots,a_1] = {Q_n\over Q_{n-1}}\quad \text{ for } n\ge 1,$$
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554021.png" /></td> </tr></table>
 
 
 
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554022.png" /> and the sequence of convergents of (1) converges to some limit <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554023.png" />, then the continued fraction (1) is called convergent and the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554024.png" /> is its value. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554025.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554026.png" />, are positive real numbers, and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554027.png" /> is real, then the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554028.png" /> of convergents of even order of (1) increases, and the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554029.png" /> of convergents of odd order decreases. Here a convergent of even order is less than the corresponding convergent of odd order (see [[#References|[5]]]).
 
 
 
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554030.png" /> is the sequence of complex numbers for which
 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554031.png" /></td> </tr></table>
+
$$[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.
  
then the expression (1) is called an expansion of the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554032.png" /> 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, [[#References|[3]]] and [[#References|[5]]]):
+
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}}).
  
1) Suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554033.png" />, that all terms of the sequences (2) and (3) are real numbers, and that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554034.png" /> for all natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554035.png" /> from some term onwards. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554036.png" /> for such <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554037.png" />, then the continued fraction (1) converges.
+
If $\def\a{\alpha}\a_0,\a_1, \dots $ is the sequence of complex numbers for which
  
2) Suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554038.png" /> and that all terms of the sequence (2) beginning with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554039.png" /> are positive. Then the continued fraction of the sequence (2) converges if and only if the series <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554040.png" /> diverges (Seidel's theorem).
+
$$\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}}):
  
The continued fraction of a sequence (2) is called regular if all its terms (except possibly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554041.png" />) are natural numbers, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554042.png" /> is an integer and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554043.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554044.png" />. For every real number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554045.png" /> there exists a unique regular continued fraction with value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554046.png" />. This fraction is finite if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554047.png" /> is rational (see [[#References|[1]]], [[#References|[2]]], [[#References|[4]]]). An algorithm for the expansion of a real number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554048.png" /> in a regular continued fraction is defined by the following relations
+
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.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554049.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
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).
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554050.png" /> denotes the integral part of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554051.png" />.
+
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
  
The numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554052.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554053.png" /> defined by (4) are called, respectively, the complete and incomplete quotients of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554054.png" /> of the expansion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554055.png" /> in a continued fraction.
+
$$
 +
\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$.
  
Around 1768 J. Lambert found the expansion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554056.png" /> in a continued fraction:
+
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.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554057.png" /></td> </tr></table>
+
Around 1768 J. Lambert found the expansion of $\tan x$ in a continued fraction:
  
Under the assumption that this continued fraction converges, A. Legendre proved that its value for rational values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554058.png" /> is irrational. It should be mentioned that in this way he proved the irrationality of the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554059.png" /> (see [[#References|[7]]]).
+
$${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
 
L. Euler found in 1737 that
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554060.png" /></td> </tr></table>
+
$${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
A real number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554061.png" /> is an irrational root of a polynomial of degree 2 with integer coefficients if and only of the incomplete quotients of the expansion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554062.png" /> in a continued fraction from some term onwards are repeated periodically (the Euler–Lagrange theorem, see [[#References|[1]]] and [[#References|[4]]]). 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554063.png" /> in a continued fraction are bounded has not been proved.
+
{{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:
 
Regular continued fractions are a very convenient tool for the approximation of real numbers by rational numbers. The following propositions hold:
  
1) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554064.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554065.png" /> are neighbouring convergents of the expansion of a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554066.png" /> in a regular continued fraction, then
+
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
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554067.png" /></td> </tr></table>
 
  
 +
$$|r-\d_n| \ge |r -\d_{n+1}|$$
 
and
 
and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554068.png" /></td> </tr></table>
+
$$\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}$.
where in the latter case equality holds only when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554069.png" />.
 
  
2) For two neighbouring convergents of the expansion of a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554070.png" /> in a regular continued fraction, at least one of them satisfies the inequality:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554071.png" /></td> </tr></table>
+
$$\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
  
3) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554072.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554073.png" /> are integers, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554074.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554075.png" /> 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.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554076.png" /></td> </tr></table>
+
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
  
then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554077.png" /> is a convergent of the expansion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554078.png" /> in a regular continued fraction.
+
$$\Big|r-{a\over b}\Big| \le |r-\d_n|,$$
 +
that $b> Q_n$ (theorem on the best approximation).
  
4) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554079.png" /> is a convergent of the expansion of a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554080.png" /> into a regular continued fraction, then for any integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554081.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554082.png" /> it follows from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554083.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554084.png" /> and
+
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.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554085.png" /></td> </tr></table>
+
The first five convergents of the expansion of $\pi$ in a regular continued fraction are:
 
 
that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554086.png" /> (theorem on the best approximation).
 
 
 
The first twenty-five incomplete quotients of the expansion of the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554087.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554088.png" /> in a regular continued fraction are:
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554089.png" /></td> </tr></table>
 
  
 +
$$\d_0 = 3,\; \d_1 = {22\over 7},\; \d_2 = {333\over 116},\; \d_3 = {355 \over 113},\; \d_3 = {103993 \over 33102}.$$
 
Therefore,
 
Therefore,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025540/c02554090.png" /></td> </tr></table>
+
$$\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.,
There exist several generalizations of continued fractions (see, e.g., [[#References|[9]]]).
+
{{Cite|Sz}}).
 
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.A. Bukhshtab,  "Number theory" , Moscow  (1966)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  B.A. Venkov,  "Elementary number theory" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.A. Markov,  "Selected works" , Moscow-Leningrad  (1948)  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.Ya. [A.Ya. Khinchin] Khintchine,  "Kettenbrüche" , Teubner  (1956)  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  A.N. Khovanskii,  "Application of continued fractions and their generalizations to problems in approximation theory" , Moscow  (1966)  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top"> , ''The history of mathematics from Antiquity to the beginning of the XIX-th century'' , '''3''' , Moscow  (1972)  (In Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top"> , ''Ueber die Kwadratur des Kreises''  (1936)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  O. Perron,  "Die Lehre von den Kettenbrüchen" , '''1–2''' , Teubner  (1954–1957)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  G. Szekeres,  "Multidimensional continued fractions"  ''Ann. Univ. Sci. Sec. Math.'' , '''13'''  (1970) pp. 113–140</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  W.B. Jones,  W.J. Thron,  "Continued fractions, analytic theory and applications" , Addison-Wesley  (1980)</TD></TR></table>
 
  
 +
====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]]).
  
 
====Comments====
 
A classical reference on convergence is [[#References|[a1]]]. Together with [[#References|[10]]], recent references are [[#References|[a2]]]–[[#References|[a4]]]. Some generalizations can be found in [[#References|[a5]]]–[[#References|[a7]]]. Except for [[#References|[a1]]], [[#References|[a8]]] 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====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> H.S. Wall,  "Analytic theory of continued fractions" , Chelsea (1973)</TD></TR><TR><TD valign="top">[a2]</TD> <TD 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)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> W.J. Thron (ed.) , ''Analytic theory of continued fractions II'' , ''Lect. notes in math.'' , '''1199''' , Springer (1986)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> C. Kraaikamp,  "The distribution of some sequences connected with the nearest integer continued fraction"  ''Indag. Math.'' , '''49'''  (1987)  pp. 177–191</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> A.J. Brentjes,  "Multidimensional continued fractions" , CWI , Amsterdam (1981)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> V.Ya. Skorobogatko,  "The theory of convergent continued fractions and its applications in numerical mathematics" , Moscow  (1983)  (In Russian)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top"> D.I. Bodnap,  "Convergent continued fractions" , Kiev (1986(In Russian)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top"> G.H. Hardy,   E.M. Wright,  "An introduction to the theory of numbers" , Oxford Univ. Press (1959)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top"> P. Henrici,  "Applied and computational complex analysis" , '''2''' , Wiley (1977)</TD></TR></table>
+
{|
 +
|-
 +
|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''' (1970pp. 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)  
 +
|}

Revision as of 13:34, 4 September 2013


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)
How to Cite This Entry:
Continued fraction. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Continued_fraction&oldid=19224
This article was adapted from an original article by V.I. Nechaev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article