Hyperbinary Numbers and Fraction Trees
Like the MTCircular? Subscribe to our free semi-annual magazine.
Questions about infinity are fascinating, and can lead into deep mathematical topics in set theory. The mathematics of infinite sets wasn’t clearly understood until Cantor defined cardinal numbers in the late 19th century, stating that two sets are the same size if there is a one-to-one correspondence between them. One surprising result from set theory, first proved by Cantor in 1873, is that there are precisely as many rational numbers (fractions) as there are counting numbers. Over one hundred years later, mathematicians Neil Calkin and Herbert S. Wilf published a more elegant proof of this fact.
This article is the result of our work to develop the ideas in the Calkin-Wilf proof, so that they would be accessible to the teachers in our three different Math Teachers’ Circles. We designed an investigation into the hyperbinary numbers (itself a 19th century topic that predates Cantor’s work on cardinality) and developed the Tree of Fractions, much in the style of Calkin and Wilf. We asked teachers to make observations, ask questions, and convince each other of the veracity of their claims.
In the binary number system, each power of two can be used at most once to represent a positive integer. Every positive integer can be written in binary in precisely one way, and we usually write the sum in order of decreasing powers of two. For example, 2710 = 110112, meaning that
= 1 x 24 + 1 x 23+ 0 x 22 + 1 x 21 + 1 x 20 = 110112
In the hyperbinary number system, each power of two can be used at most twice to represent a positive integer. This gives additional ways to represent numbers. For example, a second possible way to represent 27 in hyperbinary is
A teacher asked, “How many hyperbinary representations does 27 have?” This is exactly the question we had hoped for! More generally, what are all the ways to represent each counting number in hyperbinary? To investigate, we provided teachers with a collection of manipulatives of various shapes or colors and paper and pencils to tabulate results. One of us used a collection of tiles with different shapes, another used a box of Lucky Charms cereal, and another used 3D-printed binary coins. We agreed that each different object would represent a power of two. For example, if Triangle = 1, Diamond = 2, Square = 4, Trapezoid = 8, and Hexagon = 16, then 27 may be represented using one Hexagon, two Squares, one Diamond, and one Triangle. We also provided a data sheet with one line for each counting number up to 20, available in the Resources list below.
The table below shows the first few lines of data that the participants will produce, written in hyperbinary (participants could also choose to use symbols). In our MTCs, the teachers collaborated to ensure that the representations were correct and complete, and then entered the number of hyperbinary representations of each number into the last column, denoted by b(n).
|n||hyperbinary representations of n||b(n)|
|4||100, 20, 12||1|
|6||110, 102, 22||3|
|8||1000, 200, 120, 112||4|
|9||1001, 201, 121||3|
|10||1010, 210, 1002, 202, 122||5|
Question: What patterns do you see in the table of representations and in the values of the sequence b(n)?
Pattern 1: b(n) = b(2n+1). There are a great number of patterns to find. We were very happy when one group of teachers immediately noticed repetition in the values of b(n):
“We found that b(1) = b(3), b(2) = b(5), b(3) = b(7), b(4) = b(9), and b(5) = (11). The indices on the left side of each equality go up by 1 each time, and the indices on the right side of each pair go up by 2 each time. Thus, we conjecture that b(n) = b(2n+1).”
This is in fact the case, and we were able to prove it. Since 2n+1 is odd, we need to use a 1 shape (Triangle) to represent it in hyperbinary. Removing this 1 shape leaves the number 2n. Then, replacing each shape with the next lower shape divides the number by two, giving a representation of n.
Pattern 2: b(n) + b(2n+1) = b(2n+2). This pattern is also important, but more subtle, and so we were ready to prompt teachers toward making this observation. Proving it is just a little more complicated than proving Pattern 1, but not too much more so. Suppose we start with a representation of 2n+2. Since 2n+2 is even, the hyperbinary representation must end in a 0 or a 2. If it ends in a 0, then chopping off this last 0 results in a representation of n+1. If it ends in a 2, then chopping off this 2 has the effect of subtracting 2 then dividing by 2. Hence it yields a representation of n.
Patterns 1 and 2 determine the sequence b(n). So what is special about these two recurrence relation patterns? If we know the value of b(0) and b(1), then these two relations completely determine the value of any b(n). In other words, the four declarations
provide a complete definition of this sequence! Each odd term in the sequence is determined by a previous value, b(2n+1) = b(n). And each even term is also determined by previous values of the sequence, b(2n+2) = b(n+1)+b(n).
The Tree of Fractions
We then switched gears with our teachers, and put the hyperbinary sequence aside in order to investigate another structure with a binary nature which exhibits a lot of patterns. Secretly, we know that the teachers will soon see a connection with hyperbinary sequences!
The Calkin–Wilf binary branching tree of fractions, or Calkin–Wilf tree for short, is constructed with the following rules:
- The root node is at the top and is labeled 1/1.
- Every node has a left and right “child” node below it. If the node is labeled i/j, then its left child is labeled i/(i+j) and its right child is labeled (i+j)/j.
Participants readily observe many patterns, for example: the numerators down the left side are always 1; the denominators down the right side are always 1; the reciprocal of any number appears in the “reflected” node on the other side of the tree; and the denominator of any node is the same as the numerator of the next node to the right. We enjoyed encouraging our participants to clarify these simple observations and try to explain them. Some are easy consequences of the definition of the tree; many will be useful in the next part of the investigation.
After some discussion, participants noticed that every reduced fraction appears once and only once in the tree. It is this property that we wish to focus on. First it is helpful to break this complicated observation down into its component parts:
(b) Every positive rational number appears in the tree, and
(c) No number appears more than once in the tree.
Why is each of these three claims true? As a starting exercise, we asked the following:
Question: You were provided the rules to generate the tree “downward.” What are the rules to generate the tree “upward?” That is, if a node is labeled r/s and the node is a left child, what is its parent labeled? And if a node is labeled r/s and it is a right child, what is its parent labeled?
The proofs of all three of these claims can be carried out by starting with a “least counterexample,” which in this case means a counterexample that is as high in the tree as possible (having least level index). One then shows that it is possible to find a counterexample that is even higher in the tree, which gives a contradiction. It may be mentioned, emphasized, or formally stated, that this is equivalent to an induction-style argument on the level of the tree. For brief proofs of claims (a), (b), and (c), see our handout on proofs in the Resources list below.
Putting the two investigations together
Perhaps the most surprising observation that participants may make is that the hyperbinary numbers appear in the Calkin–Wilf tree. In fact, the sequence of denominators of each node, read left to right and then top to bottom, is exactly the hyperbinary sequence b(n). Also, the sequence of numerators, excluding the top node, is the hyperbinary sequence b(n). The remainder of our sessions focused on uncovering, at least to some extent, why this is the case.
We again started by breaking the observation down into several components. In order to describe the components, we need to number the nodes of the tree in left-to-right, top-to-bottom order.
We may now phrase our claims as follows:
(e) The fraction label of node n has the form f(n)/f(n+1) for some sequence f(n).
(f) The sequence f(n) is exactly the same as the sequence b(n) explored earlier.
The proof of claim (d) is not difficult, but does involve three cases: Node n is a left child, node n is a right child not at the end of a row, or node n is at the end of a row. Claim (e) follows immediately from claim (d).
For claim (f), we can begin with the question, “What is the left child of node n?” The answer is always node 2n+1, and this is a fun exercise on its own if there is time. This means the left child of the fraction labeled f(n)/f(n+1) is the fraction labeled f(2n+1)/f(2n+2). But then the definition of “left child” tells us that f(2n+1) = f(n) and f(2n+2) = f(n) + f(n+1). Do these statements look familiar? They should, because they are the patterns that we have said define the hyperbinary sequence b(n)!
We have arrived at the grand conclusion: If one writes out the sequence b(n), which counts the number of hyperbinary representations of n, and then makes fractions out of the successive terms in the sequence, then one obtains an enumeration of all positive rational numbers, each in lowest terms, with no repeats! This completes Calkin and Wilf’s elegant and explicit proof of Cantor’s theorem, that there are exactly as many rational numbers as there are counting numbers.
- Calkin, Neil and Wilf, Herbert S. Recounting the rationals. The American Mathematical Monthly, Vol. 107, No. 4. (2000), pp. 360-363.
- Coins in Twoland, Joshua Zucker.
- Recipe for 3D-printed binary coins
- Session handouts:
This article originally appeared in the Spring 2018 MTCircular.
|Samuel Coskey (Boise State University and Boise Math Circle), Paul Ellis (Manhattanville College and Westchester Area Math Circle), and Japheth Wood (Bard College and Bard Math Circle) learned a great deal from each other in developing this activity and writing this article, which amalgamates their different experiences leading this activity in their Circles.|