Proving that the Calkin-Wilf tree enumerates the rationals.

The Calkin-Wilf tree is an infinite undirected graph (tree) which is constructed as follows: starting from the root at $\frac{1}{1}$, each node $\frac{a}{b}$ has two children:

• a left child $\frac{a}{a+b}$
• a right child $\frac{a+b}{b}$ This tree has the property that every rational appears in it exactly once, in lowest terms. I'm interested in ways to intuitively understand this fact.

Most of what I know on this topic comes from this wonderful blog, which gives a proof [*] of the above at the link. He points out that every child uniquely defines a parent, and that every parent has a either a smaller numerator or a smaller denominator than its child. Therefore, if you start from any fraction $\frac{p}{q}$ in lowest terms, you can always trace a path back to $\frac{1}{1}$, the root.

This is a really nice proof, but it feels a bit "backwards" to me, in that we visualize walking the tree from the bottom up. Does anyone know of alternate proofs of this fact? I don't need rigor, just intuition.

Thoughts:

Clearly, all children must have either a greater numerator or a greater denominator than any of their ancestors, so they can't be repeats of an ancestor. (We also need "lowest terms" for this, but that follows by a separate argument -- see footnote).

So I'm only worried about "cousins". Perhaps there is some property that all the left children of a node share, which the right children do not? That would solve the problem, I believe.

*My summary only covers the part of his argument that proves "every rational appears in it exactly once." The "in lowest terms" part involves Euclid's Algorithm, and is covered in the next post.

• This is a very nice tree, thanks for asking the question! I'd like to include it in an upcoming class. Anyway, for walking down, I think there's at least a good heuristic you've probably thought of: Take steps to the right if your current location is less than the rational you want, otherwise left. Are you worried more about uniqueness, or existence, when walking down? – pjs36 Feb 5 '16 at 13:02
• @pjs36: Happy to spread the gospel. I suppose I'm more worried about uniqueness. So your heuristic seems to be good advice for finding a specific rational, but can we adapt it somehow to see that they will never repeat? – Eli Rose Feb 5 '16 at 15:41
• I've found this question fascinating and enjoyed the tree. I just have a couple comments to make: @pjs36 I don't think your statement about walking through the tree is true when it comes to the value of the fraction, you have to evaluate whether you want the denominator or numerator to go up individually. The second comment is this seems to be a list of all co-prime pairs of numbers where order matters. I plan to keep up to date on this post and hopefully see discussion about the uniqueness. – Connor James Feb 5 '16 at 19:37
• @ConnorJames: Yes it is! The second of the two posts I linked to has a nice explanation: mathlesstraveled.com/2008/02/06/…. He views it as Euclid's algorithm for finding the GCD of two numbers, in tree form. – Eli Rose Feb 5 '16 at 20:17

Let's use a binary encoding for our way from the top of the tree to a particular fraction. We encode the starting position and each move to the right as $\color{red}1$ while a move to the left is $\color{blue}0$. (This leads to the familiar binary representation of the Calkin-Wilf sequence.)

Now, if we move to the right, we move from $\frac ab$ to $\frac{a+b}b=\frac ab+1$. If we make $n$ consecutive steps to the right, we move from $\frac ab$ to $\frac ab+\color{red}n$, i.e. we effectively add $n$. If we move to the left, we move from $\frac ab$ to $\frac a{a+b}$, which is the same as $\frac1{1+\frac ba}$. $n$ steps to the left means moving from $\frac ab$ to $\frac1{\color{blue}n+\frac ba}$.

Now, hopefully this already rings a bell: this will lead to continued fractions! Let's take as an example $\frac 37$ which, as a continued fraction, looks like so: $$0 + \frac1{2+\frac13} = [0;2,3]$$ We can view this representation, reading it backwards, as a means to navigate the tree from the top. To reach $3$, you need three $\color{red}1$s. (The first one is for the starting point $\frac11$, the other two are to go from there to $\frac11+\color{red}2$.) To go from $3$ to $\frac1{\color{blue}2+\frac13}$, you need two $\color{blue}0$s. At that point, you're already done; the last zero means you don't need to take any more "$\color{red}1$ turns".

Here's another example. $\frac{19}{11}$ is $$1 + \frac1{1+\frac1{2+\frac1{1+\frac12}}} = [1;1,2,1,2]$$ Reading $[1;1,2,1,2]$ backwards translates to two $\color{red}1$s ($\frac{\color{red}2}1$), one $\color{blue}0$ ($\frac1{\color{blue}1+\frac12}=\frac23$), two $\color{red}1$s ($\frac23 + \color{red}2=\frac83$), one $\color{blue}0$ ($\frac1{\color{blue}1+\frac38}=\frac8{11}$), and finally one $\color{red}1$ ($\frac8{11}+\color{red}1=\frac{19}{11}$).

So, to reach any rational number, compute its continued fraction and read it backwards which'll give you a way to navigate the Calkin-Wilf tree and find the number, thereby re-creating the number, step by step, from the continued fraction. This also proves that every positive rational number actually occurs in the tree.

There's one small catch which is that you obviously must start with $\color{red}1$s and end with $\color{red}1$s (possibly, as in the first example, with zero $\color{red}1$s). Which means the continued fraction needs to consists of an odd number of pieces. This is not a problem, but rather a good thing. There are exactly two continued fraction representations for each rational number, and exactly one of them is the one we need. (For example, $\frac38$ can be written as $[0;2,1,2]$, which won't work, but also as $[0;2,1,1,1]$, which is what we need.) This proves uniqueness in the Calkin-Wilf tree.

• Very beautiful exposition. – Eli Rose Feb 9 '16 at 13:55