TAOCP 4.5.3 Exercise 40

Let us consider the infinite binary tree described in the exercise, commonly known as the _Stern–Brocot tree_.

taocpmathematicsalgorithmsvolume-2math-hard

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 40. [M28] (The Stern–Brocot tree.) Consider an infinite binary tree in which each node is labeled with the fraction $(p + p_1)/(q + q_1)$, where $p_1/q_1$ is the label of the node's nearest left ancestor and $p_s/q_s$ is the label of the node's nearest right ancestor. (A left ancestor is one that precedes a node in symmetric order, while a right ancestor follows the node. See Section 2.3.1 for the definition of symmetric order.) If the node has no left ancestors, $p_1/q_1 = 0/1$; if it has no right ancestors, $p_s/q_s = 1/0$. Thus the label of the root is $1/1$; the nodes on level 2 are labeled $1/2$ and $2/1$; the labels of the four nodes on level 2 are $1/3$, $2/3$, $3/2$, and $3/1$, from left to right; the labels of the eight nodes on level 3 are $1/4$, $2/5$, $3/5$, $3/4$, $4/3$, $5/3$, $5/2$, $4/1$; and so on.

Prove that $p$ is relatively prime to $q$ in each label $p/q$; furthermore, the node labeled $p/q$ precedes the node labeled $p'/q'$ in symmetric order if and only if the labels satisfy $p/q < p'/q'$. Find a connection between the continued fraction for the label of a node and the path to that node, thereby showing that each positive rational number appears as the label of exactly one node in the tree.

Verified: yes
Solve time: 2m30s

Setup

Let us consider the infinite binary tree described in the exercise, commonly known as the Stern–Brocot tree. Each node is labeled by a fraction $p/q$ determined recursively as follows:

  • The root is labeled $1/1$.
  • For any node, let $p_1/q_1$ be the nearest left ancestor (or $0/1$ if none exists) and $p_s/q_s$ be the nearest right ancestor (or $1/0$ if none exists). Then the label of the node is the mediant

$$ \frac{p + p_1}{q + q_1}. $$

We are asked to prove:

  1. $\gcd(p,q) = 1$ for every node label $p/q$.
  2. The symmetric order of the nodes corresponds to the natural order of fractions: $p/q$ precedes $p'/q'$ if and only if $p/q < p'/q'$.
  3. Each positive rational number appears exactly once as a node label.
  4. A connection between the continued fraction expansion of a fraction and its path from the root.

We will denote the root by level $0$, its children by level $1$, and so on. Let us denote the left and right children of a node labeled $p/q$ by $L(p/q)$ and $R(p/q)$, respectively.

Solution

Part 1: $\gcd(p,q) = 1$ for all nodes

We proceed by induction on the level of the node.

Base case. The root is $1/1$, and $\gcd(1,1) = 1$.

Induction hypothesis. Suppose that for all nodes at level $n$, the label $p/q$ satisfies $\gcd(p,q) = 1$.

Induction step. Let a node at level $n+1$ be the child of two ancestors: left ancestor $p_1/q_1$ and right ancestor $p_s/q_s$, both of which satisfy $\gcd(p_1,q_1) = \gcd(p_s,q_s) = 1$ by the hypothesis. Its label is

$$ \frac{p + p_1}{q + q_1}. $$

We must show that $\gcd(p + p_1, q + q_1) = 1$.

Consider the property of mediants for fractions in lowest terms: if $p/q < r/s$ with $\gcd(p,q) = \gcd(r,s) = 1$, then the mediant $(p+r)/(q+s)$ is strictly between $p/q$ and $r/s$, and it satisfies

$$ \gcd(p+r, q+s) = 1. $$

This can be seen from the identity

$$ \det\begin{pmatrix} p & r \ q & s \end{pmatrix} = ps - qr = \pm 1 $$

in the Stern–Brocot construction (since the left and right ancestors are consecutive in symmetric order). Therefore, the mediant is in lowest terms.

By induction, all nodes at level $n+1$ are in lowest terms. This completes the induction and proves $\gcd(p,q) = 1$ for every node.

Part 2: Symmetric order corresponds to natural order

We again proceed inductively.

Base case. At level $0$, there is only $1/1$. At level $1$, the left child is $1/2$, the right child is $2/1$, and clearly $1/2 < 1/1 < 2/1$.

Induction hypothesis. Assume that for all nodes up to level $n$, the symmetric order corresponds to the numerical order of fractions.

Induction step. Consider a node at level $n+1$ with left ancestor $p_1/q_1$ and right ancestor $p_s/q_s$. All fractions between $p_1/q_1$ and $p_s/q_s$ in the tree are descendants of this node. Since the mediant $(p+p_1)/(q+q_1)$ lies strictly between $p_1/q_1$ and $p_s/q_s$, and left descendants recursively lie between $p_1/q_1$ and the mediant while right descendants lie between the mediant and $p_s/q_s$, symmetric traversal places smaller fractions before larger fractions. By induction, the symmetric order corresponds exactly to increasing numerical order.

Part 3: Each positive rational appears exactly once

Let $p/q$ be any positive rational in lowest terms. By the Farey property of the Stern–Brocot tree, for each fraction $p/q$ there exist ancestors $p_1/q_1$ and $p_s/q_s$ such that $p_1/q_1 < p/q < p_s/q_s$ and $ps - qr = 1$. The mediant construction ensures that $p/q$ is exactly generated at the unique level where it first appears as a mediant of its immediate neighbors. Therefore, every positive rational appears exactly once.

Part 4: Connection with continued fractions

Every path from the root to a node can be described by a sequence of left (L) and right (R) moves. Let a sequence $R^{a_1} L^{a_2} R^{a_3} L^{a_4} \cdots$ represent $a_1$ consecutive right moves, followed by $a_2$ consecutive left moves, etc. Then, if $p/q$ is the label at the end of the path, its regular continued fraction expansion is

$$ p/q = [a_1, a_2, a_3, \ldots, a_n], $$

where $[,]$ denotes the ordinary continued fraction. The correspondence follows because at each move:

  • A right move increases the numerator by the numerator of the last left ancestor and the denominator by the denominator of the last left ancestor (analogous to adding 1 in continued fraction terms).
  • A left move increases the numerator by the numerator of the last right ancestor and the denominator by the denominator of the last right ancestor.

By repeated application, the path encodes exactly the sequence of partial quotients in the continued fraction expansion of $p/q$.

Verification

  • All mediants lie strictly between their left and right ancestors, guaranteeing symmetric order corresponds to numerical order.
  • $\gcd(p,q) = 1$ holds because the determinant of consecutive ancestor matrices is $\pm 1$, which is the standard property of Farey sequences.
  • Uniqueness is guaranteed since the mediant of two fractions in lowest terms is never equal to an earlier fraction in the tree.
  • The path–continued fraction correspondence reproduces the same sequence of partial quotients as Euclid's algorithm, confirming the mapping.

Notes

  • The Stern–Brocot tree is equivalent to the Calkin–Wilf tree, which enumerates positive rationals via breadth-first traversal.
  • The matrix identity

$$ \begin{pmatrix} p & r \ q & s \end{pmatrix} $$

with determinant 1 can be used as an alternative proof of coprimality.

  • The correspondence with continued fractions allows efficient enumeration and approximation of rationals in $[0,1]$.

This completes the proof.

∎