Stern-Brocot Tree

0/1 is a fraction while 1/0 is not. However, using it as such helps describe a way to get all possible positive fractions arranged in a very nice manner. So disguising 1/0 as a fraction has a very good excuse.

We already know how to obtain the mediant of two given fractions. The mediant of two fractions m₁/n₁ and m₂/n₂ is, by definition, the fraction (m₁ + m₂)/(n₁ + n₂). So, for example, from 0/1 and 1/0 we get 1/1. The mediant of 0/1 and 1/1 is 1/2 while the mediant of 1/1 and 1/0 is 2/1. On the next stage of the construction, we form four new fractions: 1/3 from 0/1 and 1/2, 2/3 from 1/2 and 1/1, 3/2 from 1/1 and 2/1, and, finally, the mediant of 2/1 and 1/0 which is 3/1. Continuing this way we get an infinite tree known as the Stern-Brocot tree because it was discovered independently by the German mathematician Moriz Stern (1858) and by the French clock maker Achille Brocot (1860).

A remarkable thing about Stern-Brocot tree is that it contains all possible non-negative fractions expressed in lowest terms and each exactly once. Just to remind, a fraction m/n is in lowest terms iff m and n are coprime, i.e, iff gcd(n,m) = 1. To prove this we'll need a series of facts of which the following is the most fundamental: if m₁/n₁ and m₂/n₂ are two consecutive (consecutive in the sense that one of them is a direct descendant of the other) fractions at any stage of the construction then

(1)	m₂n₁ - m₁n₂ = 1

This relation is true for the initial fractions: 1·1 - 0·0 = 1. Also, assuming (1) holds for two fractions m₁/n₁ and m₂/n₂, their mediant should satisfy the following two:

n₁(m₁ + m₂) - (n₁ + n₂)m₁ = 1, and
m₂(n₁ + n₂) - (m₁ + m₂)n₂ = 1

both of which are equivalent to (1).

Also, if m₁/n₁ < m₂/n₂ then

m₁/n₁ < (m₁ + m₂)/(n₁ + n₂) < m₂/n₂ ,

from which it follows that the construction of the tree preserves the natural order between the rationals. Therefore, it's impossible to obtain the same fraction twice.

And there is the last point: let a/b be a fraction in lowest terms with a and b positive. I wish to show that this fraction will appear somewhere on the tree. So long as it did not, we shall have

m₁/n₁ < a/b < m₂/n₂

for a couple of fractions m₁/n₁ and m₂/n₂ satisfying (1). These are rewritten as

n₁a - m₁b > 0 and m₂b - n₂a > 0,

which imply

n₁a - m₁b ≥ 1 and m₂b - n₂a ≥ 1.

from where

(m₂ + n₂)(n₁a - m₁b) + (m₁ + n₁)(m₂b - n₂a) ≥ m₁ + n₁ + m₂ + n₂.

An application of (1) yields

a + b ≥ m₁ + n₁ + m₂ + n₂.

with inevitable conclusion that after at most a+b steps of computing mediants one of them will be equal to a/b.

P.S.

Prof. W.McWorter has offered the following clarification to the proof:

At the root of the tree the minimum numerator-denominator sum (nd sum) is 2. At the first level of the tree the minimum nd sum is 3, and at the n-th level of the tree the minimum nd sum is n + 2. To see this, every fraction at the n-th level is the mediant of a fraction at the (n - 1)-st level and one at a higher level. The nd sum of a fraction at the (n - 1)-st level is at least n + 1 and the nd sum of a fraction at a higher level is at least 1. Hence the nd sum of their mediant is at least n + 2.

Thus, if a/b is a fraction in lowest terms not equal to any fraction in the tree, then it lies strictly between two consecutive fractions, one of which is at level a+b-1 of the tree (consecutive here is restricted to all fractions constructed up to and including level a + b - 1; none constructed beyond this level are considered). Hence by the same calculations a + b ≥ a + b + 1, a contradiction.

Remark

Pierre Lamothe from Canada informed me recently of a property of the Stern-Brocot tree I was unaware of. Pierre discovered that property in his research on music and harmony.

Let's associate with any irreducible fraction p/q the number w(p/q) = 1/pq - its simplicity. The property discovered by Pierre states that the sum of simplicities of all fractions in any row of the Stern-Brocot tree equals 1! We can easily see that this is true for a few first rows:

Row number	Tree members	Sum of simplicities
0	1/1	1/1
1	1/2, 2/1	1/2 + 1/ 2
2	1/3, 2/3, 3/2, 3/1	1/3 + 1/6 + 1/6 + 1/3
3	1/4, 2/5, 3/5, 3/4, 4/3, 5/3, 5/2, 4/1	1/4 + 1/10 + 1/15 + 1/12 + 1/12 + 1/15 + 1/10 + 1/4

The inductive proof is based on a fact (proved on later pages) that, for any fraction p/q, two fractions p/(p + q) and (p + q)/q are located just one row below that of p/q. We have an obvious identity:

w(p/(p + q)) + w((p + q)/q) = 1/p(p+q) + 1/q(p + q) = 1/pq = w(p/q),

from which it follows that if the assertion holds for one row, it holds for the next one as well.

Pierre also introduced another function W defined for the members of the tree. For an irreducible fraction p/q, Let N(p/q) denote the row of the tree that contains p/q. We start with N(1/1) = 0, N(1/2) = 1, N(2/1) = 1, N(1/3) = 2, and so on. Then the weighted simplicity W(p/q) is defined as

W(p/q) = w(p/q)·2^-N(p/q)-1

From the previous statement it then follows that the sum of all weighted simplicities of the fractions on the tree is equal to 1!

References

R.Graham, D.Knuth, O.Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
Brian Hayes, Computing Science On the Teeth of Wheels, American Scientist, July-August, Volume 88, No. 4,

71534815