5
$\begingroup$

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.

  • 1
    Considering the [Stern-Brocot tree](http://en.wikipedia.org/wiki/Stern%E2%8$0$%93Brocot_tree) might help.2012-12-17

2 Answers 2

3

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

  • 1
    Note that I placed a bounty on this question for filling this gap.2014-10-28
3

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.