Proof of the Farey sequence

Question

How would I go about proving that the Farey sequence contains all possible numbers? I'm new to number theory, so from observation the sequence looks to have all fractions. But I cannot figure out a proof that any fraction can be created with the fact that numbers in the sequence. I am using the same Farey method where you take fractions $m/n$ and $p/q$ and add them to have $\frac{m+p}{n+q}$

Answer 1

Suppose we construct a list of sequences of rational numbers (and a fake rational number number $\frac10$ which we think of as $+\infty$) by

• starting with the sequence $\frac01, \frac10$;
• taking the previous sequence, and inserting $\frac{a+c}{b+d}$ between every pair of consecutive terms $\frac ab$, $\frac cd$.

Then you want to show that every positive rational number $\frac pq > 0$ will appear eventually.

To do this, we'll need two facts:

Fact 1. The fractions in each sequence appear in increasing order.

To show this, check that if $\frac ab < \frac cd$, then $\frac ab < \frac{a+c}{b+d} < \frac cd$, so the order property is maintained as we go from each sequence to the next.

Fact 2. Consecutive fractions $\frac ab, \frac cd$ in any sequence satisfy $\frac cd - \frac ab = \frac1{bd}$.

To show this, check that if it's true, then $\frac{a+c}{b+d} - \frac ab = \frac1{b(b+d)}$ and $\frac cd - \frac{a+c}{b+d} = \frac1{(b+d)d}$, so this property is also preserved as we go from each sequence to the next.

---

Now, let's prove that every fraction $\frac pq$ will always be found.

Initially, $\frac pq$ is somewhere between $\frac01$ and $\frac10$. At each step, we'll keep track of the two consecutive terms $\frac ab , \frac cd$ such that $\frac ab < \frac pq < \frac cd$.

As long as this is true, we have $$ \frac1{bd} = \frac cd - \frac ab = \left(\frac cd - \frac pq\right) + \left(\frac pq - \frac ab\right) \ge \frac1{dq} + \frac1{qb}, $$ and by multiplying through by $bdq$, we get $q \ge b+d$. So the sum of the denominators of the fractions bracketing $\frac pq$ can never exceed $q$.

Every time we go from a sequence to the next sequence and insert $\frac{a+b}{c+d}$ between $\frac ab$ and $\frac cd$, either $\frac{a+b}{c+d} = \frac pq$ (and we are done), or $\frac ab < \frac pq < \frac{a+b}{c+d}$ (and we have our next two consecutive fractions between which $\frac pq$ must lie), or $\frac {a+b}{c+d} < \frac pq < \frac cd$ (and we have our next two consecutive fractions between which $\frac pq$ must lie).

The sum of the denominators of the fractions bracketing $\frac pq$ always keeps increasing, but it can't exceed $q$, so there can be only finitely many iterations before we stop.