3

The Stern-Brocot-Tree looks like this:

enter image description here

(image source files)

It is an infinite binary tree that contains every positive rational number as exactly one node. The children of a node $\frac{a}{b}$ are:

  • Left: Search the first left parent $\frac{x}{y}$, then: $\frac{a+x}{b+y}$
  • Right: Search the first right parent $\frac{x}{y}$, then: $\frac{a+x}{b+y}$

You start with $\frac{1}{1}$ as the root node with "parents" $\frac{0}{1}$ and $\frac{1}{0}$.

Question:

Is there any node $\frac{a}{b}$ such that it has one child $\frac{x}{y}$ with $\lfloor \log(b) \rfloor > \lfloor \log(y) \rfloor$ after completely shortening the fraction?

(Is the Stern-Brocot-Tree already completely shortened?)

Martin Thoma
  • 9,821
  • 1
    The Stern-Brocot tree contains only reduced fractions (the construction only produces reduced fractions), so the denominators in the children are strictly greater than the denominator of the node. – Daniel Fischer Oct 01 '13 at 10:33
  • Ok, I see that both questions are strongly related. When the tree only contains reduced fractions, there cannot be any node like the node I asked for as I never subtract anything from the denominator. But could you please explain why the construction only produces reduced fractions? – Martin Thoma Oct 01 '13 at 10:38

1 Answers1

3

Let's view it from the parents' viewpoint. Instead of each node containing one fraction, consider each node containing two fractions, $\left(\frac ab, \frac cd\right)$, starting with the topmost node containing $\left(\frac 01, \frac10\right)$, and producing the two children $\left(\frac ab, \frac{a+c}{b+d}\right)$ and $\left(\frac{a+c}{b+d}, \frac cd\right)$.

Now, starting from the top, it's easy to verify that we have the invariant

$$bc - ad = 1\tag{1}$$

in all nodes. For the left child, we compute

$$b(a+c) - a (b+d) = ba + bc - ab - ad = bc - ad = 1,$$

and for the right

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

So we always have the two fractions in the nodes reduced, and since the fraction in the real Stern-Brocot tree is the mediant of the two fractions, $\frac{a+c}{b+d}$, which is one of the two fractions contained in the children in our variation, the fractions in the true Stern-Brocot tree are also reduced by construction.

Hence the denominators of all children of a node in the Stern Brocot tree are always (except at the right fringe where we have the integers all with denominator $1$) strictly greater than the denominator of the node itself, since we obtain the children by adding a positive integer to the denominator (and numerator).

Daniel Fischer
  • 206,697