212 IV Continued Fractions and Their Uses
Iff 0 :=fis not the formal Laurent series of a rational function, we can write
f 0 =a 0 + 1 /f 1 ,wherea 0 = f 0 and|f 1 |>1. In the same way,
f 1 =a 1 + 1 /f 2 ,wherea 1 = f 1 and|f 2 |>1. Continuing in this way, we obtain thecontinued frac-
tion expansion[a 0 ,a 1 ,a 2 ,...]off. In the same way as for real numbers, if we define
polynomialspn,qnby the recurrence relations
pn=anpn− 1 +pn− 2 , qn=anqn− 1 +qn− 2 (n≥ 0 ),withp− 2 =q− 1 = 0 ,p− 1 =q− 2 =1, then
pnqn− 1 −pn− 1 qn=(− 1 )n+^1 (n≥ 0 ),
f=(pnfn+ 1 +pn− 1 )/(qnfn+ 1 +qn− 1 )(n≥ 0 ),and so on. In addition, however, we now have
|an|=|fn|> 1 (n≥ 1 ),from which we obtain by induction
|pn|=|an||pn− 1 |>|pn− 1 |,|qn|=|an||qn− 1 |>|qn− 1 | (n≥ 1 ).Hence
|pn|=|a 0 a 1 ···an|,|qn|=|a 1 ···an| (n≥ 1 ).From the relationqnf−pn=(− 1 )n/(qnfn+ 1 +qn− 1 )we further obtain
|qnf−pn|=|qn+ 1 |−^1 ,since
|qnfn+ 1 +qn− 1 |=|qnfn+ 1 |=|qn||an+ 1 |=|qn+ 1 |.In particular,|qnf−pn|<1 and hence
pn= qnf ,|{qnf}| = |qn+ 1 |−^1 (n≥ 1 ).Thuspnis readily determined fromqn.Furthermore,
|f−pn/qn|=|qn|−^1 |qn+ 1 |−^1 →0asn→∞.The rational functionpn/qnis called then-th convergentoff. The polynomialsanare
called thepartial quotients, and the Laurent seriesfnthecomplete quotients,inthe
continued fraction expansion off.
The continued fraction algorithm can also be applied whenfis the formal Laurent
expansion of a rational function, but in this case the process terminates after a finite
number of steps. Ifa 0 ,a 1 ,a 2 ,...is any finite or infinite sequence of polynomials with
|an|>1forn≥1, there is a unique formal Laurent seriesfwith [a 0 ,a 1 ,a 2 ,...]as
its continued fraction expansion.
For formal Laurent series there are sharper Diophantine properties than for real
numbers: