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

-