Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Farey sequence of order $n+1$ ($F_{n+1}$) can be construct by adding mediant value (${a+c \over b+d}$) into $F_{n}$, where ${a \over b}$ and ${c \over d}$ are consecutive term in $F_{n}$, and $b+d = n+1$.

I've already prove that

  • ${a \over b} < {a+c \over b+d} < {c \over d}$
  • $b+d$ always irreducible in ${a+c \over b+d}$.
  • the middle of any 3 consecutive term in any $F_{n}$ are mediant.
  • Number of new elements added is $\phi(n+1)$.

Now I wonder does the construction by mediant value coverage all elements in $F_{n+1}$. It's easy to show that ${1 \over n+1}$ and ${n \over n+1}$ does involve in it, but I have no idea how to show that other ${m \over n+a}$, where $gcd(m, n+1) = 1$, are going to be constructed.

Please give me a hint.

share|cite|improve this question
Considering the Stern-Brocot tree might help. – Joe Z. Dec 17 '12 at 3:51
up vote 2 down vote accepted

Given $0\le r\lt s$ and $\gcd(r,s)=1$, you want to show that $r/s$ shows up as a mediant. We argue by induction on $s$. Since $\gcd(r,s)=1$, there are integers $x,y$ with $$rx-sy=1$$ and $x\lt s$, $y\lt r$. By the induction hypothesis, $y/x$ and $(r-y)/(s-x)$ have already turned up in the Farey sequence, and their mediant is $r/s$.

share|cite|improve this answer
Don’t you also need to show that $y/x$ and $(r−y)/(s−x)$ are adjacent in the previous Farey sequence. Otherwise, their mediant $r/s$ would not turn up in the construction of the next Farey sequence. – Wrzlprmft Oct 18 '14 at 21:42
Good point. I think it shouldn't be hard to show that those two fractions are so close together that there can't be one between them with denominator less than $s$. – Gerry Myerson Oct 18 '14 at 22:02
Having spent some time on trying to proof this and failed, I do not consider it that easy. But then again, I am not good in number theory and may have missed something trivial. – Wrzlprmft Oct 26 '14 at 8:34
Note that I placed a bounty on this question for filling this gap. – Wrzlprmft Oct 28 '14 at 12:19

The gap in Gerry Myerson's proof can be filled easily indeed. It is easy to show by induction that $ad-bc=1$ for any two adjacent fractions $\frac{a}{b} > \frac{c}{d}$in any $F_n$. The key property is then that if $\frac{a}{b} >\frac{p}{q} > \frac{c}{d}$ with $a,b,c,d,p,q>0$, $ad-bc=1$, then $q\geq b+d$.

In fact, this last property has already been explained (by me) in an older MSE question : see here.

share|cite|improve this answer

Your Answer


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.