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.

Objective: I'd like to prove that $F_{n+1}$ (the Farey sequence of order $n+1$) is obtained form the Farey sequence $F_n$ of order $n$ by adding all fractions of the form $\frac{a+c}{b+d}$ when $\frac{a}{b}<\frac{c}{d}$ are neighbours in $F_n$ and $b+d=n+1$.

Problem: I managed to show that $\frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d}$, but I also need to show that $\frac{a+c}{b+d}$ is of the right form (i.e. that it's a completely reduced fraction), so my question is: how do I show that $gcd(a+c, b+d)=1$?

share|improve this question
add comment

3 Answers

up vote 3 down vote accepted

Neighbours $\frac{a}{b} \lt \frac{c}{d}$ in the Farey sequence satisfy

$$ bc - ad = 1$$

Now $ b(a+c) - a(b+d) = bc - ad = 1$.

Thus $\text{gcd}(a+c, b+d) = 1$.

share|improve this answer
    
+1: For the sake of completeness I recommend that the OP should prove that the identity $bc-ad=1$ holds for the other "newly created" pairs of adjacent fractions as well. –  Jyrki Lahtonen Mar 10 '12 at 18:49
    
Thanks for your help! –  sssuuusssuccc Mar 10 '12 at 21:02
    
@sssuuusssuccc: You are welcome! –  Aryabhata Mar 10 '12 at 21:02
add comment

You can define the Farey sequence of order $n$ as the sequnce of fractions occurring in-order traversal of the Stern-Brocot tree, while not descending into branches whose denominator exceeds $n$. Here one only encounters completely reduced fractions, so that is in order. The descendants of a node in the tree are obtained by adding to its numerator and denominator those of its first ancestor in the tree that is on the proper side of it (taking $\frac01$ and $\infty=\frac10$ as ultimate ancestors to ensure there is always one on either side).

If a fraction between $0$ and $1$ has denominator $n+1$ then its parent in the Stern-Brocot tree has a smaller denominator, and the first ancestor of the parent in the proper direction was next to in in the in-order traversal up to level $n$, which explains why you always get $\frac{a+c}{b+d}$ between $\frac ab$ and $\frac cd$. The relation $bc-ad=1$ holds whenever either $\frac ab$ is the first ancestor of $\frac cd$ less than it or $\frac cd$ is the first ancestor of $\frac ab$ greater than it; this follows by induction from the construction, and proves that all fractions are reduced.

share|improve this answer
add comment

It's worth remarking that this and many related properties of Farey sequences have very beautiful geometric proofs using Pick's formula and related techniques - see my answer here and its links.

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.