Show that every two consecutive rationals in any row of this infinite tree of Calkin-Wilf trees are the endpoints of a "kite".

Question

I was reading Proofs from THE BOOK, specifically, the chapter called Sets, Functions and the continuum hypothesis. In the aforementioned chapter, the following infinite tree is presented:

This is an infinite tree of sub-trees, where each sub-tree is a Calkin-Wilf tree. A Calkin-Wilf tree is formed by starting with $\frac{1}{1}$ at the top vertex and following the construction rule that any fraction $\frac{a}{b}$ generates two sons in the row below: one on its left given by $\frac{a}{a+b}$ and one on its right given by $\frac{a+b}{b}$. We denote each of these sons as left son and right son respectively. For example, $\frac{2}{3}$'s left son is $\frac{2}{2+3}=\frac{2}{5}$ and $\frac{2}{3}$'s right son is $\frac{2+3}{3}=\frac{5}{3}$.

The infinite tree of trees is generated from the sub-trees by adding a starting row of $\frac{0}{1}$'s connected to each sub-tree following the same recursion described previously, placing each sub-tree displaced horizontally by one row to the sub-tree next to it.

We also denote the $k$-fold left/right son as the $k$'th generation son, where you get to the $k$'th row following only left or right sons. For example, the $4$-fold left son of $\frac{1}{1}$ is $\frac{1}{5}$ since it's achieved by following only the left sons $4$ rows down starting from $\frac{1}{1}$. Analogously, the $2$-fold right son of $\frac{1}{2}$ is $\frac{5}{2}$ since if we go two generations down from $\frac{1}{2}$ following only right sons we get to $\frac{5}{2}$.

---

In the book, right after the construction of this infinite tree, the authors state the following proposition which I want to prove:

If we consider any nonnegative rational number $x$ in our infinite tree, then it is the $k$-fold right son of the left son of some rational $y > 0$ (for some $k > 0$), while the rational number positioned one place to the right of $x$ on the same row in the infinite tree is given as the $k$-fold left son of the right son of the same $y$.

This is a mouthful, so I tried to translate this into a diagram:

The statement thus states that for $x$ and the number one place to the right of $x$ a "common ancestor" $y$ always exists $k+1$ generations above (for some $k\in \mathbb{N}$), where the ancestor $y$ is such that: You get to $x$ following right sons of the left son of $y$, and get to the rational next to $x$ following left sons of the right son of $y$.

The above diagram resembled a "kite" shape, so to simplify the statement I define the "kite" shape as in the diagram above to re-phrase the statement as:

Show that every two consecutive rationals in any row of this infinite tree are the lower endpoints of a "kite".

---

From testing out a couple of consecutive numbers in the tree, the proposition does indeed seem to hold:

My attempt to prove the statement went something like this:

Take $2$ consecutive numbers on the tree. If they are left and right sons of the number then they form a kite with their common parent. Otherwise, the two consecutive numbers are themselves left and right children respectively of two consecutive numbers from the row above. We now ask if the consecutive numbers from the above row form a kite and repeat the previous analysis. This process must stop at some point since we have to reach the $\frac{0}{1}$ row eventually and we can't go higher, so the kite must be completed at some point.

There are some holes I can poke in my argument that I can't seem to find a way to formalize. For example, the statement that if two consecutive numbers aren't "siblings" (i.e. they're the left and right children of the same number above), then their parents are siblings. It's clear from the diagram, but I don't know how to prove this.

Another point is that I seem to be doing some kind of "informal induction" by repeating the same question to the row above, but I can't seem to find a way to formalize the proposition I'm applying the induction to, and moreover, I also don't how to formalize the "must reach $\frac{0}{1}$ condition" as a base case of said induction.

---

My question is: Does anyone know how I can fix my argument? Or alternatively, does anyone know a better way to prove the statement?

Some other useful properties that may be useful are:

• All rationals in the tree are reduced since $\gcd(a,b) = \gcd(a,a+b) = \gcd(a+b,b)$ and $\gcd(0,1) = 1$.
• If $y=\frac{a}{b} $, then its left son is $\frac{a}{a+b} = \frac{\frac{a}{b}}{1+\frac{a}{b}} = \frac{y}{1+y}$
• By induction, the $k$-fold left son of $y$ is $\frac{\left(\frac{y}{1+y}\right)}{1+(k-1)\left(\frac{y}{1+y}\right)} = \frac{y}{(1+y) +(k-1)y}= \frac{y}{1+ky}$
• If $y= \frac{a}{b}$, then its right son is $\frac{a+b}{b} = \frac{a}{b}+1 = y +1$.
• By induction, the $k$-fold right son of $y$ is $(y+1) + (k-1) = y+k$.
• Every row of the infinite tree read from left to right gives the Calkin-Wilf sequence, which lists every rational in reduced form.
• The denominator of some rational $x$ in the tree is the numerator of the number one place to the right of $x$ (on the same row).
• The sequence of the numerators of the rationals in the Calkin-Wilf sequence is the Stern-Brocot sequence.

Thank you!

Answer 1

The difficulty to prove your "kite theorem" is that the meaning of "consecutiveness" in "two consecutive rationals in any row" is not defined rigorously, although it is self-evident visually. This question is, in fact, asking how we can define that "consecutiveness" in the first place.

This answer will define that "consecutiveness", then formulating the "kite theorem" for more general situations. The generalization makes it easier to understand and prove. $\newcommand{\B}{\mathscr B} \newcommand{\lca}{\text{lca}}$

Some notations and terms on binary trees

For any two nodes $u$ and $v$ in a binary tree $\B$,

• let $d(u,v)$ be the the number of edges in the unique path between $u$ and $v$.
• let $\lca(u, v)$ be the lowest common ancestor of $u$ and $v$.
• $u$ and $v$ are on the same row (visually) $\iff$ $d(\lca(u, v),u)=d(\lca(u, v),v)$ $\iff$ $d(\alpha,u)=d(\alpha,v)$ where $\alpha$ is a common ancestor of $u$ and $v$. Being on the same row is an equivalence relation.

Visually, the left subtree, the node, the right subtree are arranged from left to right for every node. That visual arrangement is described formally by the natural total order on all nodes of $\B$. That is, $u\prec v$ iff either $u$ is in the left subtree of $v$, or $v$ is in the right subtree of $u$, or $u$ and $v$ are in the left subtree and right subtree of $\lca(u,v)$, respectively. (Note that this order has nothing to do with the values stored in the nodes.)

Visually, two consecutive nodes are on the same row without nodes sitting between them. Formally, we define two distinct nodes $u$ and $v$ as consecutive if $u$ and $v$ are on the same row without any element $z$ on the same row such that $u\prec z\prec v$ or $v\prec z\prec u$.

Kite theorem for perfect binary trees

A perfect binary tree is a tree such that every node has a father except the root, all interior nodes have a left son and a right son exactly and all leaves are on the same row.

It is straightforward to verify both the Calkin–Wilf tree and the extended Calkin–Wilf tree at the top of the question are infinite perfect binary trees without leaves. The latter one does not have a root, either.

Visually, every two consecutive nodes in a perfect binary tree are the lower endpoints of a "kite". This observation is described in the following.

Kite theorem: Let $u$ and $v$ be two nodes in a perfect binary tree $\B$. If $u$ and $v$ are consecutive, then one of them is the $k$-fold right son of the left son of $\lca(u,v)$ while the other one is the $k$-fold left son of the right son of $\lca(u,v)$, where $k=d(\lca(u,v),u)-1$.

Proof: WLOG, let $u\prec v$.

Since $u$ and $v$ are on the same row, $\lca(u,v)$ is neither $u$ nor $v$. Since the left son of $\lca(u,v)$ is not a common ancestor of $u$ and $v$, one of $u$ and $v$ is not in the left subtree of $\lca(u,v)$. Ditto for the right subtree. So $u$ is in the left subtree of $\lca(u,v)$ while $v$ is in the right subtree of $\lca(u,v)$.

Let $u'$ be the $k$-fold right son of the left son of $\lca(u,v)$. Then $u'$ is on the same row with $u$ and $v$. $u\preceq u'$, which can be proved by induction on $k$ easily. ($u'$ is, in fact, the biggest node among all nodes not lower than $u$ in the left subtree of $\lca(u,v)$.) $u'\prec v$ by definition. Had $u\not=u'$, $u'$ would have been sitting between $u$ and $v$, meaning $u$ and $v$ should not have been consecutive. So, $u=u'$.

Symmetrically, we know that $v$ is the $k$-fold left son of the right son of $\text{lca}(u,v)$. $\quad\checkmark$

---

It is easy to see that the converse of the Kite theorem is true, too.

Answer 2

To address your concerns, first we define some terms:

• Two points are considered consecutive if they are 'next to each other' on the graph - more on this later.
• Two points are siblings if they share a parent.

Now, addressing each of your concerns with your proof. To show that two consecutive points are either siblings, or their parents are consecutive, we first need a more formal definition of consecutiveness. We will use the following: Two points are consecutive if and only if they are siblings, or the left one is a right child of its parent, the right one is a left child of its parent, and the parents are consecutive.

Notice that this definition is quite natural (if you draw what it is saying), and that it also answers your concern.

Now, to formally phrase your proof, we use induction on the sum $a+b$ of the leftmost point being considered:

Base Case
Notice that if $a+b=1$, the fraction must be $\frac{0}{1}$, and so it must share a parent with the other point. This follows from the definition of consecutiveness together with the fact that $\frac{0}{1}$ is always a left child.

Therefore, they form a kite with $k=0$.

Inductive Step
Assume that the claim is true for all consecutive pairs where the leftmost fraction is $\frac{a}{b}$ with $a+b<x$. Choose any pair where the leftmost fraction is $\frac{a}{b}$, and $a+b=x$

If the two consecutive points are siblings, they form a kite with $k=0$. Otherwise the left point must be a right child of its parent, the right point must be a left child of its parent, and their parents must be consecutive (by the definition of consecutiveness). Also, left the parent of the left point be $\frac{m}{n}$, then clearly $m+n<x$ so by the assumption there must be some kite which connects them. Extending this kite by one results in the desired kite.

Since the inductive step and the base case have been proven, the claim must be true.

Answer 3

First note that if $\ x\ $ is a non-negative rational number, and $\ z\ $ the rational number positioned one place to the right of $\ x\ $ on the same row of the tree, then $\ x\ $ and $\ z\ $ could be the left and right sons, respectively, of the same node $\ y\ $. Thus, the proposition needs to be modified either by replacing the condition $\ k>0\ $ with $\ k\ge0\ $, or by excluding the possibility that $\ x\ $ and its right neighbour are both sons of the same node.

Apart from the the Calkin-Wilf tree being an (infinite) complete binary tree, there's nothing else special about it which causes the proposition (with the above mentioned modification) to hold. The proposition is true for any complete binary tree. The nodes of any such tree can be represented by binary strings $\ s\in\{0, 1\}^*\ $, with $\ \epsilon\ $ (the empty string) being the root of the tree, $\ s0\ $ is the left son of a node $\ s\ $ and $\ s1\ $ being its right son.

The following properties of an infinite such tree are easy to establish:

• A node $\ a\ $ is an ancestor of node $\ b\ $ if and only if $\ b=as\ $ for some non-empty binary string $\ s\ $.
• The latest common ancestor of two nodes $\ b\ $ and $\ c\ $, neither of which is an ancestor of the other, is the (unique) binary string $\ a\ $ such that $\ b=as_1\ $,$\ c=as_2\ $ for some non-empty binary strings $\ s_1, s_2\ $ with $\ s_{11}\ne s_{21}\ $.
• A node $\ b\ $ at level $\ \ell\ $ of the tree has binary string length $\ 2^{\ell-1}\ $.
• The nodes at any given level will be in lexicographical order when read from left to right. That is, a node $\ c\ $ will be immediately to the right of a node $\ b\ $ at the same level of the tree if and only if $\ c\ $ has the same length as $\ b\ $, $\ b<_\text{lex}c\ $, and there is no binary string $\ s\ $ of that length with $\ b<_\text{lex}s<_\text{lex}c\ $.
• A binary string $\ c\ $ is the immediate lexicographical successor of a binary string $\ b\ $ of the same length if and only if $\ b=a01^k\ $ and $\ c=a10^k\ $ for some binary string $\ a\in\{0,1\}^*\ $ and non-negative integer $\ k\ $. The node $\ b\ $ is then the $\ k$-fold right son of the left son of $\ a\ $, and the node $\ c\ $ is the $\ k$-fold left son of the right son of $\ a\ $.