Continued fractions

Solution 1:

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}$.

Solution 2:

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