Number Theory: An Introduction to Mathematics

180 IV Continued Fractions and Their Uses

with matrix

T′=

(

α′ β′

γ′ δ′

)

,

then, as is easily verified, the matrix

T′′=

(

α′′ β′′

γ′′ δ′′

)

of the composite transformation

ξ=(α′′ξ′′+β′′)/(γ′′ξ′′+δ′′)

is given by the matrix productT′′=TT′.
It follows that, if we set

Ak=

(

ak 1

10

)

,

then the matrix of the linear fractional transformation which expressesξin terms of
ξn+ 1 is

Tn=A 0 ···An.

It is readily verified by induction that

Tn=

(

pn pn− 1

qn qn− 1

)

,

i.e.,

ξ=(pnξn+ 1 +pn− 1 )/(qnξn+ 1 +qn− 1 ),

where the elementspn,qnsatisfy the recurrence relations

pn=anpn− 1 +pn− 2 , qn=anqn− 1 +qn− 2 (n≥ 0 ), (1)

with the conventional starting values

p− 2 = 0 , p− 1 = 1 , resp.q− 2 = 1 , q− 1 = 0. (2)

In particular,

p 0 =a 0 , p 1 =a 1 a 0 + 1 , q 0 = 1 , q 1 =a 1.

Since detAk=−1, by taking determinants we obtain

pnqn− 1 −pn− 1 qn=(− 1 )n+^1 (n≥ 0 ). (3)

By (1) also,