Constructing Farey sequences inductively

Question

Objective: I'd like to prove that $F_{n+1}$ (the Farey sequence of order $n+1$) is obtained form the Farey sequence $F_n$ of order $n$ by adding all fractions of the form $\frac{a+c}{b+d}$ when $\frac{a}{b}<\frac{c}{d}$ are neighbours in $F_n$ and $b+d=n+1$.

Problem: I managed to show that $\frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d}$, but I also need to show that $\frac{a+c}{b+d}$ is of the right form (i.e. that it's a completely reduced fraction), so my question is: how do I show that $gcd(a+c, b+d)=1$?

Answer 1

Neighbours $\frac{a}{b} \lt \frac{c}{d}$ in the Farey sequence satisfy

$$ bc - ad = 1$$

Now $ b(a+c) - a(b+d) = bc - ad = 1$.

Thus $\text{gcd}(a+c, b+d) = 1$.

Answer 2

You can define the Farey sequence of order $n$ as the sequnce of fractions occurring in-order traversal of the Stern-Brocot tree, while not descending into branches whose denominator exceeds $n$. Here one only encounters completely reduced fractions, so that is in order. The descendants of a node in the tree are obtained by adding to its numerator and denominator those of its first ancestor in the tree that is on the proper side of it (taking $\frac01$ and $\infty=\frac10$ as ultimate ancestors to ensure there is always one on either side).

If a fraction between $0$ and $1$ has denominator $n+1$ then its parent in the Stern-Brocot tree has a smaller denominator, and the first ancestor of the parent in the proper direction was next to in in the in-order traversal up to level $n$, which explains why you always get $\frac{a+c}{b+d}$ between $\frac ab$ and $\frac cd$. The relation $bc-ad=1$ holds whenever either $\frac ab$ is the first ancestor of $\frac cd$ less than it or $\frac cd$ is the first ancestor of $\frac ab$ greater than it; this follows by induction from the construction, and proves that all fractions are reduced.

Answer 3

It's worth remarking that this and many related properties of Farey sequences have very beautiful geometric proofs using Pick's formula and related techniques - see my answer here and its links.