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
    $\begingroup$ +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. $\endgroup$ – Marc van Leeuwen Apr 19 '12 at 6:53
  • $\begingroup$ Related... $\endgroup$ – J. M. is a poor mathematician Apr 19 '12 at 6:57

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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.