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.

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|improve this question
    
Considering the Stern-Brocot tree might help. –  Joe Z. Dec 17 '12 at 3:51
add comment

1 Answer

up vote 1 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|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.