The nth Farey Sequence, F_n, is the sequence of rational numbers a/b, such that GCD(a,b)=1, and 0 ≤ a ≤ b ≤ n.  For example,

F₅ is {0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1}

If a/b and c/d are successive terms of a Farey sequence, then bc - ad=1.   That is, the product of the means minus the product of the extremes is 1.

The denominators, b and d, of adjacent elements of a Farey sequence are coprime, because numbers x and y exist such that bx+dy=1.  In fact, x and y are the numerators (the first one negative) of these adjacent elements.

Similarly, the numerators, a and c, of adjacent elements of a Farey sequence are coprime, because ax+cy=1, where x=-d and y=b.

Mediant

The "mediant" of two fractions expressed in lowest terms, a/b and c/d, is (a+c)/(b+d).  For example,

the mediant of 2/5 and 1/2 is (2+1)/(5+2) = 3/7

Each element of a Farey Sequence that has two neighbors is the mediant of those two neighbors.  For example, in F₅, 3/5 lies between 1/2 and 2/3, and 3/5 is the mediant of 1/2 and 2/3.

Let a/b, c/d, e/f be successive elements of a Farey Sequence,
so bc-ad=1 and de-cf=1.
Thus bc-ad+cf-de=0.
Rearranging this, d(a+e)=c(b+f), so c/d=(a+e)/(b+f)

This fact can be used to find F_n+1 given F_n.  For each pair of successive elements of Fn in which the sum of their denominators equals n+1, the mediant can be inserted between them to form F_n+1.  The mediants formed this way will always be in lowest terms because both the denominators and numerators of adjacent elements of a Farey Sequence are coprime, and the sum of two coprime numbers is coprime to each of them.

Farey Sunburst

Letting F₆ = {y₁/x₁, y₂/x₂, ...} the (x,y) pairs are plotted on a lattice, occupying the first half of the first quadrant (i.e. the first octant).  To complete the starburst, this sequence is repeated seven more times with reflections about the line y=x and the axes. 

Farey Triangle

The image to the right shows F₅, extended the same way, and blown up so you can see the sequence of triangles formed with the origin and two successive elements of a F₅.

I will call a lattice triangle a "Farey Triangle" if its vertices are (0,0), (x₁,y₁), and (x₂,y₂), or one of its seven other reflections, where x₁/y₁ and x₂/y₂ are adjacent elements of a Farey sequence.  The Farey Triangles in the diagram to the right are the thin triangles with yellow interior and one vertex at the origin.

It is fairly easy to see that the area of each of the Farey triangles is 1/2.  Since its vertices are (0,0), (a,b), (c,d), its area is |ad-bc|/2.  And since a/b and c/d are successive elements of a Farey sequence, |ad-bc|=1, proving the result.

Relationship of Farey Sequences to Pick's Theorem

From the origin, we will call a lattice point (x,y) "visible" if GCD(x,y)=1.  Two lattice points (x₁,y₁), (x₂,y₂), in which the largest x- or y- coordinate (in absolute value) is n, will be called n-Farey-adjacent if, from the point of view of the origin, no other lattice point with coordinates no larger than n is visible between them.

A triangle formed by the origin and two n-Farey-adjacent lattice points is a Farey triangle, and (as proved above) has an area of 1/2.

Conversely, a lattice triangle whose longest side's longest component measures n units, and whose border contains only the three lattice points of its vertices, and whose interior has no lattice points is congruent to a Farey triangle, because viewed from one end of its longest side, the other two vertices are n-Farey-adjacent.

Internet References

Mathworld: Farey Sequence 

Cut-the-knot: Farey Sequence and its application to Pick's Theorem  

Related pages in this website

Pick's Theorem, for finding the area of lattice polygons.

The area of a triangle with vertices (0,0), (a,b), (c,d) is |ad-bc|/2. 

See also Recurrence Relation

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]