The Stern-Brocot Tree

As with the Farey series, the Stern-Brocot tree is built using mediant fractions. Place two starting terms 0/1 and 1/0 some way apart and their mediant fraction 1/1 in between and a little down. This creates two gaps: one between 0/1 and 1/1 and another between 1/1 and 1/0. Compute two corresponding mediants and place them below 1/1. Continue in this manner. The next step will add a row of four fractions, then eight, and so on.

When building the Farey series, mediants sometimes have to be reduced to lowest terms. For example, in F₅, (2 + 3)/(5 + 5) = 1/2. This never happens with the Stern-Brocot tree. The fact is proved by induction based on the following property of the tree: any two fractions m₁/n₁ and m₂/n₂ whose mediants will be computed at any stage of the construction, satisfy

A mediant fraction generated by two terms that satisfy (1) stands in the same relation with both of its progenitors. From this we observe that the rows of numerators and denominators of the terms in the Stern-Brocot tree are computed independently of each other. They may be dealt with separately. The row of numerators starts with the pair of integers 0,1. The row of denominators starts with the pair of integers 1,0. They are just symmetric reflections of each other. Let denote the first tree as [0,1] and the second [1,0]. We may generalize and consider trees that grow from an arbitrary pair of integers [x,y].

Since, at any stage of construction, we only carry out linear operations (actually only addition), we get a whole vector space of trees. The space is 2-dimensional as we can write [x,y] = x[1,0] + [0,1]. Each tree [x,y] consists of two parts: the left tree [x,x+y] =x[1,1] + y[0,1] and the right tree [x+y,y] = x[1,0] + y[1,1]. The tree [1,1] is a mirror image of itself. In particular, all its rows are palindromic.

Let's record several observations:

1. The tree of the denominators [1,0] has [1,1] as its left part.
2. The left part of the tree of the numerators [0,1] is still [0,1] while [1,1] is now the right part.
3. Fractions on the left from 1/1 are less than 1; fractions on the right from 1/1 are greater than 1

Surprisingly, the Stern-Brocot tree contains all non-negative fractions. Therefore, its left subtree contains all fractions between 0 and 1. Somehow it must be possible to pluck off the tree the Farey series of any order. Whatever the exact process, since the only criterion for a fraction to belong to the Farey series is the magnitude of its denominator, and, as we know, the right part of any row of denominators is palindromic, the same will be true for the denominators in the Farey series.

• Pick's Theorem
  • Pick's Theorem, A Proof
  • Farey Series
  • Pick's Theorem Applies to the Farey Series
  • Stern-Brocot Tree

Copyright © 1997 Alexander Bogomolny