Stern-Brocot Tree

Fine features

My knowledge of the Stern-Brocot tree comes from the book Concrete Mathematics by Graham, Knuth, and Patashnik. In the Bibilography section they list two works by Brocot and one by Stern. In addition to his original article, Achille Brocot published (1862) a 97 page monograph devoted to what is now known as the Stern-Brocot tree. The author being a clockmaker, both publications appeared under the same title of "Calcul des rouages par approximation, nouvelle méthode." ("Cogwheel computations by approximation, a new method.") The original article by M.Stern "Ueber eine zahlentheoretische Funktion" took up 27 pages in Journal für die reine und angewandte Mathematik 55 (1858). (Having never learned German, I believe I got a reasonably correct translation of the title with the help of an online German-English dictionary.)

It's impossible to judge contents of an article by its title. Chances are that in the combined 124 pages Stern and Brocot discussed a variety of the tree's features. However, the simple discussion that follows does not appear in Concrete Mathematics but is a result of a couple of hours of pondering over the diagram and a fruitful email exchange with Professor W. McWorter.

We start with an observation that in every layer (row) of the Stern-Brocot tree, fractions are arranged in a sequence such that the sequence of numerators is the same as the sequence of denominators except that the order is reversed. Let's then talk of the numerators only. Following are a few first rows of the numerators:

Row number Tree members
-1 0, 1
0 1
1 1, 2
2 1, 2, 3, 3
3 1, 2, 3, 3, 4, 5, 5, 4
4 1, 2, 3, 3, 4, 5, 5, 4, 5, 7, 8, 7, 7, 8, 7, 5

I numbered rows in such a way as to have 2n members in row #n starting with n=0. One salient feature which is easily noticeable is that any row appears as the first half of its immediate successor. A less obvious feature provides a clue to the nature of the second half. The second half is also uniquely determined by the previous row. In order to obtain it write the previous row first as is and then in the reverse order and sum the two up. For example, row #2 is 1, 2, 3, 3. This is the first half of row #3. To obtain the second half write two copies of row #2 (straight and reverse):

1, 2, 3, 3
3, 3, 2, 1

and add them termwise to get 4, 5, 5, 4. Thus the third row is 1, 2, 3, 3, 4, 5, 5, 4. This is also the first half of the fourth row. To get the other half write this sequence twice:

1, 2, 3, 3, 4, 5, 5, 4
4, 5, 5, 4, 3, 3, 2, 1

Summing up gives 5, 7, 8, 7, 7, 8, 7, 5. This is a nice feature whose origin I'll try to explain in the remainder of the page.

First let's generalize our framework. The Stern-Brocot tree (of numerators) starts with the numbers 0 and 1. But the same procedure may apply to any pair of numbers x and y. Let's denote the resulting tree as [x,y]:

Row number Tree members
-1 x, y
0 x + y
1 2x + y, x + 2y
2 3x + y, 3x + 2y, 2x + 3y, x + 3y

Recollecting the notion of vectors and vector spaces, we note that every tree [x, y] is expressed as a combination of two basic trees: [x, y] = x[1, 0] + y[0, 1]. The latter [0, 1] is the Stern-Brocot tree; [1,0] is its mirror reflection. Each tree [x, y] consists of two parts: the left subtree [x, x + y] and the right subtree [x + y, y] which grow (upside down) quite independently of each other. The last observation we shall need is that, for any x, the tree [x, x] is symmetric with respect to the vertical line through the midpoint of every row. This is so as we just observed that [x, x] = x[1, 0] +x[0, 1], and the two trees [0, 1] and [1, 0] are reflections of each other.

Returning to the Stern-Brocot tree [0, 1], its left subtree is [0, 0 + 1] = [0, 1] which is exactly the same. Its right subtree [0 + 1, 1] = [1, 1] = [0, 1] + [1, 0] is the sum of [0, 1] and its mirror image [1, 0].

Corollary

  1. For n ≥ 0, the sum of all terms in the row #n is 3n.

    The proof is by induction. The claim is obviously true for n = 0. The first half of row #(n + 1) is simply row #n; the second half comprises two versions of row #n: straight and reversed. And the claim follows.

  2. The sum of all terms in the Stern-Brocot tree up to and including row #n is 1 + 1 + 3 + 9 + ... + 3n = 1 + (3n+1-1)/2.

Originally, the Stern-Brocot tree is constructed in stages by inserting new (mediant) fractions between the fractions formed on the previous stages. The property we just discussed leads to an alternative construction wherein rows grow by appending new terms rather then through insertion. Appending procedure also applies to the totality of the terms and not only to the rows of the tree. Zigzagging between the fractions and their ancestors let's list the numerators of fractions constructed up to the stage n of the procedure (and excluding the opriginal 0 and 1):

Construction stage Tree members
0 1
1 1, 1, 2
2 1, 1, 2, 1, 3, 2, 3
3 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4

Note the ever present 1 in the middle of each row. Disregarding this 1, every row is obtained from the previous one the same way as before. For example, to move from stage #1 to stage #2 first write the three already constructed terms: 1, 1, 2. Next append the middle 1. Finally apply the "reflect then add" step:

1, 1, 2
2, 1, 1

to obtain the remainder of the third stage: 3, 2, 3. All together: 1, 1, 2, 1, 3, 2, 3.

In practical terms, this approach is extremely inefficient as an ever increasing portion of the tree regenerates on every stage.

Remark

The sequence of integers formed by the successive rows of the table is now recorded as sequence # in the On-Line Encyclopedia of Integer Sequence.

|Contact| |Front page| |Contents| |Generalizations|

Copyright © 1996-2018 Alexander Bogomolny

 63043599

Search by google: