PlanetMath: convergents to a continued fraction

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (197)
Orphanage
Unclass'd
Unproven (498)
Corrections (25)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

convergents to a continued fraction

(Theorem)

Definition.The $n^{\mathrm{th}}$ convergent to a continued fraction $[a_0,a_1,a_2,a_3,\ldots]$ is the value of the fraction obtained by cutting off the fraction after , i.e. the value of $[a_0,a_1,\ldots,a_n]$ .

Write

$\displaystyle p_0$	$\displaystyle =a_0$	$\displaystyle p_1$	$\displaystyle = a_0 a_1+1$
$\displaystyle q_0$	$\displaystyle = 1$	$\displaystyle q_1$	$\displaystyle = a_1$

so that

$\displaystyle [a_0]=a_0 =\frac{p_0}{q_0}$
$\displaystyle [a_0,a_1]=a_0+\frac{1}{a_1} = \frac{a_0a_1+1}{a_1}=\frac{p_1}{q_1}$

For

, define

$\displaystyle p_n$	$\displaystyle = a_n p_{n-1}+p_{n-2}$	(1)
$\displaystyle q_n$	$\displaystyle = a_n q_{n-1}+q_{n-2}$

Theorem 1 The $n^{\mathrm{th}}$ convergent to $[a_0,a_1,a_2,a_3,\ldots]$ is given by

$\displaystyle [a_0,\ldots,a_{n-1},a_n]=\frac{p_n}{q_n}$

where are defined as above.

Proof. Induction. For

$\displaystyle [a_0,\ldots,a_{n-1},a_n]$	$\displaystyle =[a_0,\ldots,a_{n-1}+\frac{1}{a_n}]$
	$\displaystyle =\frac{\left(a_{n-1}+\frac{1}{a_n}\right)p_{n-2}+p_{n-3}}{\left(a_{n-1}+\frac{1}{a_n}\right)q_{n-2}+q_{n-3}}$
	$\displaystyle =\frac{a_n(a_{n-1}p_{n-2}+p_{n-3})+p_{n-2}}{a_n(a_{n-1}q_{n-2}+q_{n-3})+q_{n-2}}$
	$\displaystyle =\frac{a_n p_{n-1}+p_{n-2}}{a_n q_{n-1}+q_{n-2}}$
	$\displaystyle =\frac{p_n}{q_n}$

$\qedsymbol$

Theorem 2 For $n\geq 1$ , the numbers $\frac{p_{n-1}}{q_{n-1}}$ and $\frac{p_n}{q_n}$ are a Farey pair; in fact,

$\displaystyle p_nq_{n-1}-p_{n-1}q_n=(-1)^{n-1}$

(2)

and thus

$\displaystyle \frac{p_n}{q_n}-\frac{p_{n-1}}{q_{n-1}}=\frac{(-1)^{n-1}}{q_{n-1}q_n}$

(3)

Proof. This is again a simple induction. The statement is true for

. For

, we have

$\displaystyle p_nq_{n-1}-p_{n-1}q_n$	$\displaystyle =(a_n p_{n-1}+p_{n-2})q_{n-1} - p_{n-1}(a_n q_{n-1}+q_{n-2})$
	$\displaystyle = p_{n-2}q_{n-1} - p_{n-1}q_{n-2} = -(-1)^{n-2} = (-1)^{n-1}$

$\qedsymbol$

Note that if $[a_0,a_1,\ldots]$ is a simple continued fraction, then the above theorem implies that $\gcd(p_n,q_n)=1$ , since any common factor of and must divide .

Theorem 3 For $n\geq 2$ ,

$\displaystyle p_nq_{n-2}-p_{n-2}q_n=(-1)^n a_n$	(4)
$\displaystyle \frac{p_n}{q_n}-\frac{p_{n-2}}{q_{n-2}}=\frac{(-1)^na_n}{q_{n-2}q_n}$	(5)

Proof. Similar to the proof of the above theorem. $\qedsymbol$

Theorem 4 If $[a_0,a_1,\ldots]$ is a simple continued fraction, then $q_n\geq n$ and, for , .

Proof. This follows directly from the iterative definition for the

and the fact that the

are positive integers. $\qedsymbol$

These results easily imply the following important convergence theorem:

Theorem 5 For any continued fraction, the even convergents $p_{2n}/q_{2n}$ are strictly monotonically increasing, and the odd convergents $p_{2n+1}/q_{2n+1}$ are strictly monotonically decreasing. In addition, every odd convergent is greater than each even convergent. If the continued fraction is simple, then the limit of the odd convergents is equal to the limit of the even convergents, and thus the continued fraction has a well-defined value equal to their common limit.

Proof. This is basically obvious from the previous observations. Write

for the $n^{\mathrm{th}}$ convergent, i.e.

$\displaystyle c_n=\frac{p_n}{q_n}$

Each

is positive, so

$\displaystyle c_n-c_{n-2}=\frac{(-1)^na_n}{q_nq_{n-2}}$

is positive for

even and negative for

odd. This proves the observations about monotonicity. Also,

$\displaystyle c_n-c_{n-1}=\frac{(-1)^{n-1}}{q_nq_{n-1}}$

is positive for

odd, so that

$\displaystyle c_{2n+1}>c_{2n}$

(6)

Now, if for some

we had $c_{2j+1}\leq c_{2k}$ , then $j\neq k$ by (6). If

, then since the even convergents increase, $c_{2j+1}\leq c_{2k}<c_{2j}$ , while if

, then since the odd convergents decrease, $c_{2k+1}<c_{2j+1}<c_2k$ . In either case, this contradicts (6).

As to the statement about simple continued fractions, it is clear that the even (odd) convergents converge since they form a monotonically increasing (decreasing) sequence that is bounded below (above). But

$\displaystyle \left\lvert\frac{p_{2n}}{q_{2n}}-\frac{p_{2n-1}}{q_{2n-1}}\right\rvert=\frac{1}{q_{2n}q_{2n-1}}\leq \frac{1}{2n(2n-1)}\to 0$

and thus the limits are identical. $\qedsymbol$

Next we prove the following theorem regarding the connection between the “tail” of a continued fraction, its convergents, and its value:

Theorem 6 If $x=[a_0,a_1,\ldots]$ is a simple continued fraction, write $t_n=[a_n,a_{n+1},\ldots]$ for $n\geq 0$ (the $n^{\mathrm{th}}$ complete convergent). Then

$\displaystyle x = \frac{p_{n-2}+t_np_{n-1}}{q_{n-2}+t_nq_{n-1}}$

Proof. This is another simple proof by induction. Note that

$\displaystyle t_n = [a_n,a_{n+1},\ldots] = a_n+\frac{1}{t_{n+1}}$

so that

$\displaystyle t_{n+1} = \frac{1}{t_n-a_n}$

Then

$\displaystyle \frac{t_{n+1}p_n+p_{n-1}}{t_{n+1}q_n+q_{n-1}} = \frac{\frac{1}{t_... ...nq_{n-1}+q_{n-2})+q_{n-1}} = \frac{t_np_{n-1}+p_{n-2}}{t_nq_{n-1}+q_{n-2}} = x$

$\qedsymbol$

Finally, we derive a bound on how well the convergents approximate the value of the continued fraction:

Theorem 7 If $x=[a_0,a_1,\ldots]$ is a simple continued fraction, then

$\displaystyle \left\lvert x-\frac{p_n}{q_n} \right\rvert < \frac{1}{q_n^2}$

Proof.

$\displaystyle x-\frac{p_n}{q_n}$	$\displaystyle = \frac{p_{n-1}+t_{n+1}p_n}{q_{n-1}+t_{n+1}q_n}-\frac{p_n}{q_n}$
	$\displaystyle = \frac{q_np_{n-1}+t_{n+1}p_nq_n - p_nq_{n-1}-t_{n+1}p_nq_n}{q_n(q_{n-1}+t_{n+1}q_n)} = \frac{q_np_{n-1} - p_nq_{n-1}}{q_n(q_{n-1}+t_{n+1}q_n)}$
	$\displaystyle = \frac{(-1)^n}{q_n(q_{n-1}+t_{n+1}q_n)}$

But $t_{n+1}>a_{n+1}$ , so that $q_{n-1}+t_{n+1}q_n > q_{n-1}+a_{n+1}q_n = q_{n+1}$ and thus

$\displaystyle \left\lvert x-\frac{p_n}{q_n} \right\rvert = \frac{1}{q_n(q_{n-1}+t_{n+1}q_n)} < \frac{1}{q_nq_{n+1}} < \frac{1}{q_n^2}$

since the

are strictly increasing. $\qedsymbol$

Bibliography

1: G.H. Hardy & E.M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Oxford Science Publications, 1979.

"convergents to a continued fraction" is owned by rm50.

(view preamble)

Also defines:

convergent, complete convergent

Log in to rate this entry.
(view current ratings)

Cross-references: strictly increasing, bound, bounded, sequence, decreasing, converge, monotonicity, negative, obvious, well-defined, limit, addition, monotonically decreasing, odd, monotonically increasing, strictly, even, integers, positive, proof, similar, factor, implies, simple continued fraction, simple, Farey pair, numbers, induction, fraction, continued fraction
There are 17 references to this entry.

This is version 5 of convergents to a continued fraction, born on 2008-05-21, modified 2008-05-23.
Object id is 10606, canonical name is ConvergentsToAContinuedFraction.
Accessed 390 times total.

Classification:

AMS MSC:	11A55 (Number theory :: Elementary number theory :: Continued fractions)
	11J70 (Number theory :: Diophantine approximation, transcendental number theory :: Continued fractions and generalizations)
	11Y65 (Number theory :: Computational number theory :: Continued fraction calculations)

Pending Errata and Addenda

None.

Discussion

forum policy

No messages.

Interact