Continued fractions

I'd really love with concluding that for given integers $a_0,a_1,...a_N$ with $a_i>0$ for $i>0$, representing the continued fraction $[a_0; a_1,....,a_N]$, with the following recursion:

$p_{-1}=1, q_{-1}=0, p_o=a_0, q_o=1, p_s=a_sp_{s-1}+p_{s-2}, q_{s}=a_sq_{s-1}+q_{s-2}$

we can get that $[a_0; a_1,....,a_N]=\frac{p_s}{q_s}$.

I tried to do that with induction, the basic step for $s=0$ is trivial, assuming that it is correct for $n$ , how do I prove it for $n+1$? I tried to use the data that was given, but I'm not sure how.

Thank you very much

-
+1 This is a very pertinent question, which I find very little addressed in texts about continued fractions: if you want to compute successive convergents, you can do this with minimal calculation passing from one approximation to the next, without having to re-evaluate to continued fraction from the inside out at one level deeper. I'd have to think a bit for the right formula; I'm not sure it's the one you give (try and show some examples please). Careful study of the Stern-Brocot tree is the key. – Marc van Leeuwen Apr 19 '12 at 6:53
Related... – J. M. Apr 19 '12 at 6:57

2 Answers

I think the easiest approach to this question is to associate to each finite continued fraction symbol $[a_0; a_1,....,a_N]$ not just a rational number, but a $2\times 2$ matrix with natural number entries, namely the matrix product $$M(a_0,a_1,....,a_N)= \pmatrix{a_0&1\\1&0} \cdot \pmatrix{a_1&1\\1&0} \cdots \pmatrix{a_N&1\\1&0}$$ The first column of this matrix (its value when applied to $\tbinom10$) gives numerator and denominator of the value of the continued fraction $\alpha=[a_0; a_1,....,a_N]$, as follows from the definition of continued fractions by an immediate induction on $N$. But the matrix gives more information about the position of $\alpha$ in the Stern-Brocot tree, or more precisely that of its descendant $\alpha'=[a_0; a_1,....,a_N,1]$ "continuing in the same direction" (which serves as starting point for continued fractions that start with $[a_0; a_1,....,a_N,\ldots]~$). The sum of the columns of $M(a_0,a_1,....,a_N)$ (its value on $\tbinom11$) gives the numerator and denominator of $\alpha'$, while the second column (its value on $\tbinom01$) gives the closest ancestor of $\alpha'$ at the opposite side with respect to $\alpha$, which is also (if $N>0$) the previous convergent $\beta=[a_0; a_1,....,a_{N-1}]~$.

Personally I think these matrices are the most useful objects to work with; lots of stuff is easy in terms of them, for instance the fact that their determinant is $(-1)^{N+1}$ is immediate from the definition. Also descending to a next convergent needs just one previous matrix, and involves a simple right multiplication. From this one can easily deduce a recurrence formula of order $2$ for the convergents in reduced form. Indeed if these convergents are $\frac{p_i}{q_i}$ in reduced form as in the question, then by the above description $$M(a_0,a_1,....,a_{s-1})=\pmatrix{p_{s-1}&p_{s-2}\\q_{s-1}&q_{s-2}}$$ for $s\geq2$, and $$M(a_0,a_1,....,a_{s-1},a_s)=\pmatrix{p_s&p_{s-1}\\q_s&q_{s-1}} = M(a_0,a_1,....,a_{s-1})\cdot \pmatrix{a_s&1\\1&0}$$ from which one easily deduces $p_s=p_{s-1}a_s+p_{s-2}$ and $q_s=q_{s-1}a_s+q_{s-2}$.

-

Check pp. 4–5 in Khinchin's book (in Google Books).

-