How to prove that construction of Farey sequence by mediant is coverage?

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

• ${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.

-
Considering the Stern-Brocot tree might help. –  Joe Z. Dec 17 '12 at 3:51

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

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

-