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
 A: 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}$.
A: Check pp. 4–5 in Khinchin's book
(in Google Books).
