Farey Neighbours
Farey sequences are lists of fractions in ascending order of magnitude. Can you prove that in every Farey sequence there is a special relationship between Farey neighbours?
Age
16 to 18
Challenge level
Problem
You may wish to explore Farey Sequences and Mediant Madness before working on this problem.
The Farey sequence $F_n$ is the list written in increasing order of all the rational numbers between $0$ and $1$ that have only the numbers $1, 2, 3, ... n$ as denominators. We have $$\eqalign{F_1&=\frac{0}{1}, \frac{1}{1}\cr F_2&=\frac{0}{1}, \frac{1}{2}, \frac{1}{1}.}$$
For the two rational numbers $\frac{a}{c}$ and $\frac{b}{d}$ the mediant is defined as $\frac{a+b}{c+d}$.
Show that if $0< \frac{b}{d} < \frac{a}{c}< 1$ then $\frac{b}{d} < \frac{a+b}{c+d} < \frac{a}{c}$.
Each Farey sequence $F_{n+1}$ must contain all of the terms of $F_{n}$, along with some new terms. Each 'new' term in the Farey sequence $F_{n+1}$ is the mediant of two consecutive terms in $F_n$, but not all mediants of consecutive terms of $F_n$ are included: where the denominator of the mediant is greater than $n+1$ the mediant does not occur in $F_{n+1}$ and instead two consecutive terms in $F_n$ are repeated in $F_{n+1}$.
Use the mediants to work out $F_3, F_4$ and $F_5$.
Two consecutive terms in a Farey sequence are known as Farey Neighbours.
Let $\frac{b}{d}$ and $\frac{a}{c}$ be Farey Neighbours. Choose some pairs of Farey Neighbours from the Farey Sequences you have worked out, and calculate $ad-bc$.
What do you notice?
Can you prove it using mathematical induction?
This is the key result that links Farey sequences to infinite sets of circles that are packed together, each circle touching its neighbours. See the problem Ford Circles.
The Farey sequence $F_n$ is the list written in increasing order of all the rational numbers between $0$ and $1$ that have only the numbers $1, 2, 3, ... n$ as denominators. We have $$\eqalign{F_1&=\frac{0}{1}, \frac{1}{1}\cr F_2&=\frac{0}{1}, \frac{1}{2}, \frac{1}{1}.}$$
For the two rational numbers $\frac{a}{c}$ and $\frac{b}{d}$ the mediant is defined as $\frac{a+b}{c+d}$.
Show that if $0< \frac{b}{d} < \frac{a}{c}< 1$ then $\frac{b}{d} < \frac{a+b}{c+d} < \frac{a}{c}$.
Each Farey sequence $F_{n+1}$ must contain all of the terms of $F_{n}$, along with some new terms. Each 'new' term in the Farey sequence $F_{n+1}$ is the mediant of two consecutive terms in $F_n$, but not all mediants of consecutive terms of $F_n$ are included: where the denominator of the mediant is greater than $n+1$ the mediant does not occur in $F_{n+1}$ and instead two consecutive terms in $F_n$ are repeated in $F_{n+1}$.
Use the mediants to work out $F_3, F_4$ and $F_5$.
Two consecutive terms in a Farey sequence are known as Farey Neighbours.
Let $\frac{b}{d}$ and $\frac{a}{c}$ be Farey Neighbours. Choose some pairs of Farey Neighbours from the Farey Sequences you have worked out, and calculate $ad-bc$.
What do you notice?
Can you prove it using mathematical induction?
This is the key result that links Farey sequences to infinite sets of circles that are packed together, each circle touching its neighbours. See the problem Ford Circles.
Getting Started
Start by constructing some Farey Sequences.
Find out more about the mediant of two fractions in Mediant Madness.
If you haven't yet met Proof by Induction, you may like to read this article.
For your proof by induction, your inductive hypothesis could be that if $\frac bd$ and $\frac ac$ are Farey Neighbours with $c,d \leq n$, then $ad-bc=1$.
Then consider which fractions can be Farey Neighbours of $\frac bd$ and $\frac ac$ in $F_{n+1}$.
Student Solutions
We received a very clear solution from Amrit, proving using induction that for any Farey Neighbours, $ad-bc=1$.
Here is Amrit's Solution.
Here is Amrit's Solution.
Teachers' Resources
Why do this problem?
The problem provides purposeful practice on inequalities and leads to a proof using mathematical induction.It also builds on the problems Farey Sequences and Mediant Madness, and provides a foundation for the beautiful and surprising result in Ford Circles.
Possible approach
For a geometrical approach to proving that $\frac{b}{d} < \frac{a+b}{c+d} < \frac{a}{c}$, you may wish to start with Mediant Madness.To prove algebraically that $\frac{a+b}{c+d} < \frac{a}{c}$, given that $\frac bd < \frac ac$, you may need to offer the hint to rearrange to get $bc < ad$, and add $ac$ to both sides of the inequality.
Next, invite students to use Mediants to quickly calculate the first few Farey Sequences, and calculate $ad-bc$ for a few pairs of Farey Neighbours.
Once they establish that $ad-bc=1$ for the examples they try, invite them to construct a proof by induction to show that it holds for all Farey Neighbours.
Key questions
What are we trying to show?Is there anything we can do to both sides of the inequality we have, to get us to the inequality we want?
If two fractions are Farey Neighbours in $F_n$, will they still be Farey Neighbours in $F_{n+1}$?
If they are not Farey Neighbours in $F_{n+1}$, what will the new fraction between them be?
Possible extension
After working on this problem, students could explore Ford Circles.
Possible support
Farey Sequences and Mediant Madness can be used to ease students into the exploration of the ideas in this problem.This article on Mathematical Induction may also be useful.