Notes on a Fibonacci tree

(Last updated: 2024/3/31)

So Beren Gunsolus came up with this nifty rule for generating a tree that is full of Fibonacci numbers, he and I and some others (Astra Kolomatskaia, Ophelia, Emma C) figured out what's going on with it, and now I want to tell you about it.¹

Beren defined the tree iteratively. The root is 1. Then, at each step, we find the smallest number in the tree that does not have any children², and give it two children; the left child is the smallest not yet in the tree, and the right child is the sum of the parent and the left child.

Here's a partial picture of what it looks like, having given children to every number up to 21:

                                         1
                         /---------------+-----------------\
                         |                                 |
               /---------2-------\                 /-------3-------\
               |                 |                 |               |
        /------4---\         /---6---\         /---5---\       /---8---\
        |          |         |       |         |       |       |       |
     /--7--\    /-11-\    /-10-\  /-16-\     /-9-\  /-14-\  /-13-\  /-21-\
     |     |    |    |    |    |  |    |     |   |  |    |  |    |  |    |
  /-12\ /-19\ /18\  29  /17\  27 26   42   /15\ 24  23  37  22  35  34  55
  |   | |   | |  |      |  |               |  |
/20\ 32 31 50 30 48    28  45             25  40
|  |
33 53

If you stare at this a while, you'll likely notice some patterns, like the Fibonacci numbers going down the right-hand side, or the Fibonacci numbers minus one going down the left hand side, or any of the many other ways that Fibonacci numbers appear in the tree.³ You may also notice some relations that hold but aren't obvious from the original construction; like, for instance, not only does the parent plus the left child equal the right child, but also, the left child plus the right child equals the left child of the right child.⁴

So what is this tree?

So, is there some nice description of the tree that explains all of this, that isn't based on this iterative building rule? Yes! You've probably heard of Zeckendorf representation, which is like "base Fibonacci" (for the purposes of Zeckendorf the Fibonacci sequence starts 1, 2, 3, 5,...), with the digits being 0 and 1, and the restriction being that there can never be two conseuctive ones. Well it turns out there's such a thing as dual Zeckendorf, which is the same thing, except that instead the restriction is that you can't have consecutive zeroes (the implicit 0's before the initial 1 don't count).⁵

It turns out that dual Zeckendorf is the key to Beren's tree, if we just subtract 1 from each number (so now 0 is the root). If we subtract 1 from each number, then the root is the empty string, taking the left child corresponds to appending 1, and taking the right child corresponds to appending 10. Every legal dual Zeckendorf representation can be made uniquely in this way, so the tree contains each whole number exactly once, as we saw earlier.

Proof of the dual Zeckendorf description

To prove this⁷, let's divide positive integers into "cold" numbers, that end with a 1 in dual Zeckendorf, and "hot" numbers, that end with a 0 (the number 0 is neither). We're going to work in the adjusted tree, which is going to obey the rule R'(n)=n+L'(n)+1 (here L', R' denote the adjusted operations for this adjusted tree). Now, we'll group hot and cold numbers into pairs, where a cold number m will be paired with the hot number m:0, the colon denoting concatenation. So in each pair, the cold number is always smaller.

So, assume as an inductive hypothesis that the theorem is true for all numbers already in the tree; this means that cold and hot numbers have been added in pairs. Then, when we go to process a number n, and we want to determine L'(n), well, L'(n) cannot be hot, because each excluded hot number has a smaller cold number that is also excluded. So L'(n) must be cold, and the smallest excluded cold number is (applying the inductive hypothesis) n:1. Then to determine R'(n) we simply add n, L'(n), and 1, and this addition yields n:10. This proves the claim.

Now this new description of the tree may strike you as obviously related to some other trees, or cause you to ask hey what about such-and-such a natural-seeming variant, but, we'll get to variants down below. First, let's give a third description of the tree!

Another description, this one parity-based

But there's yet another description of Beren's tree, one based on ordinary Zeckendorf and not dual Zeckendorf, and one that doesn't require adjusting the tree by subtracting one from everything.

Write the original tree in ordinary Zeckendorf. The root is 1. Then, to get the children of a given node, if the node ends in an even number of zeroes, then the left child appends 0 and the right child appends 00. While if the node ends in an odd number of zeroes, then the left child appends 1, while the right child appends 01.

I know of two ways to prove this equivalence. The first is to once again adapt Ophelia's cold/hot argument to this new description, proving its equivalence with Beren's original description. This adaptation is straightforward and I won't belabor it.

The second is to directly prove its equivalence with the dual Zeckendorf description; I'm going to relegate that one to the footnotes. ⁸

The reading sequence and its inverse

Now let's get to the really good stuff.

Let's say we read across the rows of the tree, in order, from left to right. If we do this, we get the sequence

1, 2, 3, 4, 6, 5, 8, 7, 11, 10, 16, 9, 14, 13, 21...

Beren plugged this into OEIS and found that it's A232560, which is defined as the inverse permutation of A232559, which is in turn obtained from reading across a different tree (there's a picture of it at the link). This other tree is a tree of doubling or adding 1. It has 1 as the root, and each node has two children; for the left child you add 1, for the right child you double. Well, except that actually not every node has two children -- if we did that, the tree would be full of duplicates, so, we only allow adding 1 to numbers that are even. Odd numbers only get a single child.

From this description, this second tree doesn't seem to have anything to do with Fibonacci numbers! Why would it be somehow inverse to the first tree?

That's not the only seemingly odd thing here either. The second tree isn't even a binary tree. If the trees had the same shape, then we could regard these two permutations not as being on the linearly-ordered natural numbers, but rather on the nodes of the unlabeled tree of that shape, and show that the permutations were inverse that way, and then we'd never have to involve this whole "reading sequence" business. But since they're not the same shape, that means that in our two reading order sequences, the row boundaries are falling in different places. And yet they're inverse to each other!

Well, it turns out that there's a nice explanation, and that the shape of the tree is actually not a problem but rather the solution. You see, the tree that we started with was a tree based on Fibonacci numbers and (dual) Zeckendorf representation, but in shape it was a binary tree. The second tree is based on binary representation, but its shape is Fibonacci!

If you actually draw the second tree, you'll see the lengths of the rows are Fibonacci. Of course they are; it's doing the whole Fibonacci rabbit thing. Only even-valued nodes (adult rabbits) can have two children, with odd-valued nodes (juvenile rabbits) having only one.

So, we have a Fibonacci binary tree, and a binary Fiboncci tree. The inverse relation makes a bit more sense now, no?

Switching from binary to bijective binary

To actually prove it, we'll want to start by subtracing 1 from each number in both trees, so the roots are now 0 rather than 1. These are the versions of the trees we'll work with. As you know, when you do this to Beren's tree, you get the dual Zeckendorf tree; 0 is the root (empty string), left child means appending 1, right child means appending 0.

What about our other tree? Well, if we don't subtract 1, then it's a tree of binary representations; 1 is the root; even numbers have two children, with the left child corresponding to changing the final 0 to a 1, and the right child corresponding to appending 0; and odd numbers have one child, corresponding to appending 0.

OK, but what if we do subtract 1? Well, then it's a tree of bijective binary representations! The doubling operation becomes double-and-increment. So now 0 (the empty string) is the root; it's odd numbers that have two children, with the left child meaning you change the final 1 to a 2, and the right child meaning you append a 1; and even numbers have only one child, corresponding to appending a 1.

Proof core of the inverse relation

Anyway, having made the adjustments above, time to start the work of the proof. In order to see that these trees have inverse reading permutations, I want to introduce two auxiliary trees. We have a Fibonacci binary tree and a binary Fibonacci tree, but for comaprison, I'm going to introduce a binary binary tree and a Fibonacci Fibonacci tree.

That is to say -- consider the binary tree that, when read across, simply yields 0, 1, 2, 3, etc. This, if we look at it in bijective binary, can be described as a tree with root 0 (the empty string), where the left child is append a 1, and the right child is append a 2.

We can do the same thing on the other side; we can take a tree as the same shape as our Fibonacci-shaped tree of bijective binary numbers, but one whose reading sequence is simply 0, 1, 2, 3, etc. This similarly has a natural interpretation in terms of dual Zeckendorf; left children mean append a zero, right (or only) children mean you append a 1. Only numbers that are a 1-child can have a 0-child.¹⁰

So: Let us consider the permutation that takes our binary binary tree (whose reading sequence is just the whole numbers) to our Fibonacci (dual-Zeckendorf) binary tree (which has the same shape). What does it do to the number at any given spot? Well, what you do to the number is, you write the number in bijective binary; then you change each 2 to a 10 while leaving each 1 as a 1; then you interpret the string as dual Zeckendorf. So that's our permutation one way.

Now, we consider the permutation that takes our Fibonacci Fibonacci tree (whose reading sequence is just the whole numbers) to our binary Fibonacci tree (which has the same shape). What does this do to the number at any given spot? Well, you write the number in bijective binary; then, starting with the empty string, you interpret each 1 as an "append 1" and each 0 as a "change the final 1 to a 2" (because a 0-child must have a parent that is a 1-child, this is well-defined); then you interpret the string as bijective binary. That's our permutation the other way.

And, well, those two operations are inverse to each other, so there you go! Where did we use the reading order? How did we deal with the fact that the two trees are different shapes? By setting up two auxiliary trees which, although they had different shapes from each other, had identical reading sequences. Basically we had a chain of four trees, FB-BB-FF-BF, where the pairs FB-BB and FF-BF have the same shape, while the pairs BB-FF have the same reading sequence.

Variants and relations among them

Ordinary Zeckendorf and ordinary binary

Now, you may have noticed here that we used dual Zeckendorf and bijective binary, with roots starting from 0. But what if we had used ordinary Zeckendorf, with root starting from 1? Where the left child meant "append 0" and the right child meant "append 01"? Well, in that case, the same argument as above implies that our corresponding "inverse" tree would be a tree based on ordinary binary, with 1 as the root... a tree that is almost the same as our original double-or-increment tree, before we subtracted 1 from everything. The only difference? It'd be flipped left-to-right. That tree had the left child meaning "change the final 0 to a 1" (when there were two children) and the right child meaning "append a 0"; here it would be the other way around.

Another parity-based tree

But there's more! What if we took this ordinary Zeckendorf tree, and subtracted 1 from everything? Well, then, obviously, the reading permutation would be inverse to that of our flipped tree but with 1 subtracted from everything. The interesting part is that this tree has an alternate characterization!

Namely, this new tree, if we write it in dual Zeckendorf, follows a parity rule like we saw earlier! The root is 0 (the empty string), and if a node ends in an even number of ones, then the left child appends 1 and the right child appends 11; while if the node ends in an odd number of ones, then the left child appends 0, while the right child appends 10.

One can prove this using an analogue of the parity proof from earlier; it's exactly analogous, so I won't bother writing it out.¹¹

Now let's double everything

OK, but what if we took our Zeckendorf and dual-Zeckendorf-based trees and flipped those? Obviously, the +1/-1 relations between them would still hold. But would we once again get binary-based trees giving the inverse reading permutation?

Yes! I won't bother proving it because again it's the same as above, but we'd once again get trees based on binary or bijective binary, only now, we'd be decrementing instead of incrementing.

That is to say, for the trees based on ordinary binary, your options would be to append a 1, or, if the number ends with a 1, to change the final 1 to a 0; and for bijective binary, you could append a 2, or change the final 2 (if there is one) to a 1.

Summary with diagram of relations

To summarize, here's a list of the (nontrivial) involved trees and the relations between them.

Each tree I'll notate by two letters. The first letter will be one of:

Z, for trees based on Zeckendorf representation
D, for trees based on dual Zeckendorf
B, for trees based on binary representation
b, for trees based on binary reprsentation but with decrements
J, for trees based on bijective binary
j, for trees based on bijective binary but with decrements

If the first letter is Z or D, the second letter will be one of:

B, for binary trees in forward order (right child is larger)
b, for binary trees in reverse order (left child is larger)
P, for parity-based binary trees in forward order
p, for parity-based binary trees in reverse order

If the first letter is B or J, the second letter will be one of:

D, for trees in forward order
Z, for trees in reverse order

(This last notation may seem strange, but -- considering that the larger number is the one where a digit is appended rather than altered -- forward order vs reverse order determines whether the tree is shaped in such a way that position in the tree corresponds to Zeckendorf representation (reverse order) or dual Zeckendorf (forward order).)

Trees beginning with Z, B, or b will use 1 as the root, while trees beginning with D, J, or j will use 0 (the empty string) as the root. For clarity, I'll put the root in brackets after the name of the tree.

Beren's original tree is ZP[1].

We then get the following diagram of relations among the trees:

               inverse        flip          inverse
        jD[0] -------- Db[0] ------ DB[0] ---------- JD[0]
      -1/|               /-1        -1/              -1/|
       / |              /            /                / |
      /  |flip         /            /                /  |
   +1/   |            /+1  flip  +1/     inverse  +1/   |
 bD[1] --+--------- Zp[1] ------ ZP[1] --------- BD[1]  |flip
    |    | inverse                                 |    |
    |    |                                         |    |
    |    |    inverse         flip        inverse  |    |
flip|  jZ[0] --------- Dp[0] ------ DP[0] ---------+-- JZ[0] 
    |   /-1              /-1        -1/            |   /-1
    |  /                /            /         flip|  /
    | /                /            /              | /  
    |/+1  inverse     /+1  flip  +1/     inverse   |/+1
   bZ[1] --------- Zb[1] ------ ZB[1] ---------- BZ[1]

By the way, you may be wondering, what about bijective Zeckendorf? Unfortunately, it doesn't seem to fit nicely into the picture above.

A quick but disappointing generalization to higher Fibonacci analogues

Finally, before we change gears, let's look at one more way we can get similar inverse relations.

Define the t-Fibonacci numbers to be the sequence that starts with t 1's, and then obeys the recurrence F_t,k=F_t,k-1+F_t,k-t. So the 1-Fibonacci numbers are the powers of 2, while the 2-Fibonacci numbers are the Fibonacci numbers.

A number of facts transfer from the Fibonacci setting to the t-Fibonacci setting (I'll omit the proofs). One has t-Zeckendorf representations, where we require that any two 1's have at least t-1 0's between them. These exist, are unique, and can be compared lexicographically. One also has bijective t-Zeckendorf; again, representations exist, are unique, can be compared lexicographically, and have a relation to ordinary t-Zeckendorf that's similar to the t=2 case. (The number you have to adjust by is t, and the prefix you have to strip off is 10^t-1.) And one has dual t-Zeckendorf; once again, this exists, is unique, and can be compared lexicographically.

Unfortunately, not everything works so well. Notably, the well-definedness of left-shift on pseudo-t-Zeckendorf does not hold for t=3. And while dual t-Zeckendorf exists, it's not clear how to sensibly put it in a tree for t>2.

Still, one can at least make an ordinary t-Zeckendorf tree for any t; the root is 1, edges are either 0 (left) or 1 (right), and you can't have a 1 edge except after t-1 consecutive 0 edges. We might call this tree Z^tZ^t, following the pattern above (where Z² means the same thing as Z and Z¹ means the same thing as B). Of course, such a tree is not that interesting; its reading sequence will simply be the positive integers. What we want to know is about mixing values of t, like we did above with t=1 and t=2, to get more interesting trees.

Well, if t'<t, we can make the tree Z^tZ^t' by having edges be either 0 (left) or 0^t-t'1 (right); the latter can't occur except after t'-1 consecutive 0s. Notably we can take t'=1 and get Z^tB. Unfortunately, if we subtract 1 from each number in Z^tB, and write the results in dual-t-Zeckendorf, we don't seem to get any nice rule when, say, t=3.

Now if t'=t+1, we can make the tree Z^tZ^t+1 where edges are either 0 (left) or "change final 0 to a 1" (right); the latter can occur only after t consecutive 0's. Unfortunately, I don't see how to make an analogous tree Z^tZ^t' for t'>t+1.

Still, if you do this, then the trees Z^tZ^t+1 and the trees Z^t+1Z^t will have inverse reading permutations! But for t>1, this fact doesn't seem to fit into a nice big diagram like the one above for t=1; it's fairly isolated. You can I'm sure write down trivial variants on it that will also be true, but for nontrivial variants, I'm not aware of any.

Back to the original characterization: Handling the variants

Can we characterize some of these variants in the same way we originally generated Beren's tree? Yes, we can!

Beren's tree ZP uses 1 as the root and obeys n+L(n)=R(n). When you subtract 1 to get the tree DB, it uses 0 as the root and obeys n+L(n)+1=R(n). (In this section I'll just use L(n) and R(n) to mean the left and right child in the tree under discussion, not necessarily the original tree ZP.)

Let's generalize this. For c≥1, we'll define T_c,0, or just T_c, to be the 0-rooted tree, generated like Beren's tree but with the law n+L(n)+c=R(n). We'll also define T_c,1 to be the 1-rooted tree defined analogously but with n+L(n)+(c-1)=R(n). We subtract 1 from the contstant so that T_c,1 is equal to T_c,0 with 1 added to each node.

Then, as noted above, T_1,0=DB, and T_1,1=ZP. But the trees T_2,0 and T_2,1 are also trees that were discussed above! Namely, T_2,1=ZB. One can prove this using the usual hot/cold-style argument. This means that T_2,0=DP. One can prove this either by noting that T_2,0=T_2,1-1=ZB-1=DP, or one can again prove it hot/cold style. The latter approach, I suppose, would also function as an alternate proof that DP=ZP-1.

Let's make this into a table:

T_1,0 = DB
T_1,1 = T_1,0+1 = ZP
T_2,0 = DP
T_2,1 = T_2,0+1 = ZB

OK, but what about T₃ and up?

Higher constants

Well, I actually have an answer to this question (although I've only currently proven it for c≤5), but it gets pretty hairy as c increases, so I think I'm not going to cover it here. This page was supposed to be about those inverse permutations and this isn't relevant to that! I'll write about those some other time.

To give you a bit of the flavor of it, though... let S(n) denote the Zeckendorf left-shift operations. Then with c=1 (sticking to the 0-rooted trees), we have L(n)=S(n)+1. With c=2, we have L(n)=S(n+1)-1. With c=3, we have L(n)=S(n+2)-3... unless n is of the form F_k-3, then L(n)=S(n+2)-3+(-1)^k. A little funky, right? And the exceptions grow thicker from there... and quadratically so! But again, I'll write about that some other time...

(back to main page)

¹Could this be a paper? Probably, assuming the main parts turn out to be original, but first I'm making this quick informal public writeup so that I have something to cite when I add this information on OEIS! Formalizing everything to make it a paper can come eventually, meanwhile I've got other papers I need to get out...

²This is always well-defined, because the tree contains no duplicates. Each new left child can't be a duplicate by definition. Each new right child must be bigger than the corresponding parent and left child, which, since parents are processed in order and left children are added in order, means that it must also be bigger than each existing left child and each existing parent. But also, from the monotonicity of addition, it must also be bigger than each existing right child, since each is a sum of a parent and a left child, and this new one is the sum of the largest parent and largest left child. (Also, the tree contains all positive integers, due to the rule for generating left children. So it contains each positive integer exactly once.)

³OK, you want a list of ways that we've found? OK. Here, L(n) means the left child of n, while R(n) means the right child of n.

The obvious one: Rⁿ(1)=F_2n+2 and LRⁿ(1)=F_2n+3
The slightly less obvious one I've already mentioned: L^k(1)=F_k+3-1.
A generalization of the previous two: RⁿL^k(1)=F_2n+k+3-F_2n+1 and LRⁿL^k(1)=F_2n+k+4-F_2n+2.
One more: L²Rⁿ(1)=F_2n+4+1 and RLRⁿ(1)=F_2n+5+1.

⁴You want a list of what we found there too? OK. Again, L(n) means the left child of n, while R(n) means the right child of n.

This one holds by definition: n+L(n)=R(n)
The less obvious one I've already mentioned: L(n)+R(n)=LR(n).
A related one, but don't try to generalize, it won't work: L²(n)+LR(n)=L²R(n).
One that explains the RLRⁿ(1) rule: RL(n)=LR(n)+1.
Also: L²(n)=R(n)+1. Combining the previous few, we then get R(n)+RL(n)=L²R(n).

⁵Speaking of Zeckendorf variants, there's also bijective Zeckendorf! As in, instead of 0 and 1, you use 1 and 2, and you can't have two consecutive 2's.⁶ Now, famously bijective binary holds a special relation with ordinary binary, where the bijective binary for n is the same as the ordinary binary for n+1, but with the initial 1 stripped off and each digit incremented by 1. A similar relation holds for bijective Zeckendorf; the bijective Zeckendorf for n is the ordinary Zeckendorf for n+2 but with the initial 10 stripped off and each digit incremented.

⁶Note that there's no such thing as dual bijective Zeckendorf, because in such a system it would be impossible to represent the number 3. (Actually, I won't prove it here, but n cannot be represented in dual bijective Zeckendorf iff n+3 starts with 1001 in ordinary Zeckendorf; for those numbers that can be represented, the representation is unique.)

⁷This proof is primarily due to Ophelia.

⁸This proof will rely on the following nontrivial fact about Fibonacci numbers: If we consider "pseudo-Zeckendorf representations", that is, Zeckendorf representations with no consecutivity restrictions, then the "left shift" operation (appending a 0) is well-defined. I'm going to relegate the proof of that to a separate footnote.⁹

Anyway, suppose w is the Zeckendorf representation of n, and w ends in k zeroes, so w=w'0^k; w' is then also a Zeckendorf representation of some number n', and w' ends in a 1. Let v be the Zeckendorf representation of n'-1, which, since w' ends in a 1, is simply w' with its final 1 changed to a 0. Therefore, the value of v0^k is n-f_k, where here by f_k I mean F_k+2 (that conflicts with another convention, I know, sorry).

Now let u be the dual Zeckendorf representation of n'-1; by the lemma, the value of u0^k is therefore also equal to n-f_k. So, if k is even with k=2ℓ, then u':=u(10)^ℓ has value n-f_k+(f_k-1)=n-1, and is also in dual Zeckendorf; so it's the dual Zeckendorf representation of n-1. Similarly, if k is odd with k=2ℓ+1, then u':=u(10)^ℓ1 has value n-f_k+(f_k-1)=n-1, and it too is in dual Zeckendorf, so once again it's the dual Zeckendorf representation of n-1.

Now let's consider what happens as n varies. Going by the above, if k is even, then u' ends in a 0; so appending 1 to u' corresponds to appending 0 to w, and appending 10 to u' corresponds to appending 00 to w.

On the other hand, if k is odd, then u' ends in a 1. Appending 1 to u' is the same as appending 0 and then incrementing; so this corresponds to appending 0 to w and then incrementing, which appends a 1. Similarly, appending 10 to u' we can think of as appending 01 and then incrementing; so this corresponds to appending 00 to w and then incrementing, which appends a 01. This completes the proof.

⁹It suffices to show that if w is a pseudo-Zeckendorf representation representing the number n, and v is the Zeckendorf representation of n, then w0 and v0 again represent the same number. Note that v0 is again a Zeckendorf representation, so we are showing that the number represented by w0 has Zeckendorf representation v0.

To show this, note that any pseudo-Zeckendorf representation can be converted to Zeckendorf representing the same number by the following procedure: Find the leftmost "11" (which cannot be preceded by another 1 or it would not be leftmost), then change this "011" to a "100"; repeat until there are no 11's (and this procedure must terminate because the number of 1's decreases with each step). Now observe that this procedure (both each step and the termination condition) commutes with appending a 0. This proves the claim.

¹⁰The identity of these two descriptions of the tree might not be obvious, but it follows from the fact that to compare two numbers written in dual Zeckendorf, you just do so lexicographically. This in turn can be proven by comparing the smallest possible dual Zeckendorf number of a given length with the largest possible dual Zeckendorf number that's one shorter in length.

¹¹Note that this proof needs to use the fact that appending 1 to pseudo-Zeckendorf representations is well-defined. You could prove this by first proving it for 0, as done above, and then note that appending 1 is just appending 0 and then incrementing; or you could do it directly, mimicking the above proof for 0, except you'd use dual Zeckendorf instead of Zeckendorf.

(back to main page)