182 IV Continued Fractions and Their Uses
wherebnandcnare integers andcn>0. We can write
bn=ancn+cn+ 1 ,wherean= ξn andcn+ 1 is an integer such that 0≤cn+ 1 <cn. Thusξn+ 1 is defined
if and only ifcn+ 1 =0, and thenξn+ 1 =cn/cn+ 1. Since the sequence of positive
integers{cn}cannot decrease for ever, the continued fraction algorithm for a rational
numberξalways terminates. At the last stage of the algorithm we have simply
ξN=aN,whereaN>1ifN>0. The uniquely determined finite sequence [a 0 ,a 1 ,...,aN]is
called the continued fraction expansion ofξ.
Convergentsandcomplete quotientscan be defined as before; all the properties
derived forξirrational continue to hold forξrational, provided we do not go past
n=N. The relation
ξ=(pN− 1 ξN+pN− 2 )/(qN− 1 ξN+qN− 2 )now shows that
ξ=pN/qN.Consequently different rational numbers have different continued fraction expansions.
Now leta 0 ,a 1 ,a 2 ,...be any infinite sequence of integers withan≥1forn≥1.
If we define integerspn,qnby the recurrence relations (1)–(2), our previous argu-
ment shows that the sequence{p 2 n/q 2 n}is increasing, the sequence{p 2 n+ 1 /q 2 n+ 1 }is
decreasing, and the two sequences have a common limitξ. If we putξ 0 =ξand
ξn+ 1 =−(qn− 1 ξ−pn− 1 )/(qnξ−pn)(n≥ 0 ),our previous argument shows also thatξn+ 1 > 1 (n≥ 0 ).Since
ξn=an+ξn−+^11 ,it follows thatan= ξn . Henceξis irrational and [a 0 ,a 1 ,a 2 ,...] is its continued
fraction expansion.
Similarly it may be seen that, for any finite sequence of integersa 0 ,a 1 ,...,aN,
withan≥1for1≤n
[a 0 ,a 1 ,...,aN] as its continued fraction expansion.
We will write simplyξ=[a 0 ,a 1 ,...,aN]ifξis rational andξ=[a 0 ,a 1 ,a 2 ,...]
ifξis irrational.
We will later have need of the following result:
Lemma 0Letξbe an irrational number with complete quotientsξnand convergents
pn/qn.Ifηis any irrational number different fromξ, and if we defineηn+ 1 by
η=(pnηn+ 1 +pn− 1 )/(qnηn+ 1 +qn− 1 ),then− 1 <ηn< 0 for all large n.
Moreover, ifξ> 1 andη< 0 ,then− 1 <ηn< 0 for all n> 0.