Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
+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
add comment

2 Answers 2

up vote 4 down vote accepted

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; lost 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. However 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}$.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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