I am going to tell you some surprising facts about Fibonacci numbers. These were first explained to me by John Conway in an alcove in Fine Hall in Princeton in 1996. I believe that Clark Kimberling also had a hand in discovering them; I don’t know how to apportion credit. Subsequently, various friends of mine (Dima Fon-Der-Flaass, Daniele Gewurz and Francesca Merola) worked on generalisations. But I am not discussing generalisations here; I will stick to the original setting. You can find a bit more information (including proofs) here.
I am going to make an inessential change from the last post, and start with the numbers F1=1 and F2=2. (In other words, I am not considering F0 at the moment.) The sequence of Fibonacci numbers starting with F1 is
|1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, …|
Every non-negative integer can be written as a sum of distinct powers of 2 in a unique way: this is just the standard expression for numbers in base 2, for example
|100 = 64 + 32 + 4 = 1100100 (in base 2).|
In a similar way, every non-negative integer can be written as a sum of distinct Fibonacci numbers, with the extra proviso that no two of the summands are consecutive in the Fibonacci sequence. Without this proviso, the uniqueness obviously fails: 13 = 8+5, for example.
The expression is found by being greedy. Given a number N, let Fk be the largest Fibonacci number not exceeding N; then we take Fk as one of the summands, and note that Fk−1 cannot also occur (or else N ≥ Fk+Fk−1 = Fk+1, contrary to our assumption). So then we just have to express N−Fk as a sum of non-consecutive Fibonacci numbers, which is taken care of by that wonderful tool, induction.
|100 = 89 + 11 = 89 + 8 + 3.|
I will call this the Fibonacci representation of N.
The Fibonacci representation has a counting interpretation. Given the first n Fibonacci numbers, we can write every number from 0 to Fn+1−1 uniquely using them, with no two consecutive. Any representation can be coded by a string of length n of As and Bs with no two consecutive Bs: we put A or B in the kth position to denote the absence or presence of the kth Fibonacci number. So the number of numbers we are representing (which is Fn+1) is equal to the number of strings of length n with no two consecutive Bs, as we saw in the preceding post.
Using this representation, we can define the Fibonacci successor function σ on the natural numbers as follows. Given N, write it as the sum of non-consecutive Fibonacci numbers; then σ(N) is obtained by simply replacing each Fibonacci number in the sum by the next one. For example,
|σ(100) = 144 + 13 + 5 = 162.|
Note that σ(Fk) = Fk+1. So we have a second method of generating the Fibonacci numbers: start with the number 1 and repeatedly apply the function σ.
More generally, we can start with any number N and produce a sequence in this way, whose terms are N, σ(N), σ(σ(N)), …. Then we find:
For any N, the sequence produced in this way satisfies the Fibonacci recurrence; each term after the first two is the sum of the two preceding terms.
This is, quite simply, because if N = Fi+Fj+…, then
|σ(σ(N))||=||Fi+2 + Fj+2 + …|
|=||(Fi+Fi+1) + (Fj+Fj+1) + …|
|=||N + σ(N).|
In other words, there are some “special” sequences satisfying the Fibonacci recurrence, which can be specified by just a single initial term.
A little thought shows that a number N is equal to σ(M) if and only if the number F1=1 does not occur in its Fibonacci representation.
Now we produce a table of numbers as follows. We start with the usual Fibonacci sequence (which can be obtained by beginning with 1 and then applying σ repeatedly). Then we take the smallest number which didn’t already occur (which happens to be 4), and apply σ to it repeatedly – or, after the first application of σ, use the Fibonacci recurrence. Since the Fibonacci representation of 4 is 3+1, the sequence continues 5+2=7, 11, 18, 29, …. Then repeat the procedure, always beginning with the smallest number which has not yet occurred.
The table begins as follows. (Ignore the first two columns for the moment.)
|0||1||1, 2, 3, 5, 8, 13, …|
|1||3||4, 7, 11, 18, 29, 47, …|
|2||4||6, 10, 16, 26, 42, 68, …|
|3||6||9, 15, 24, 39, 63, 102, …|
|4||8||12, 20, 32, 52, 84, 136, …|
|5||9||14, 23, 37, 60, 97, 157, …|
Now every positive integer occurs just once in the table. For consider any number N: either it occurs, or at a certain point it is the smallest number which has not yet occurred, in which case we put it at the start of a row. The numbers which start rows are just those which are not Fibonacci successors, that is, those whose Fibonacci representations contain the number 1.
In particular, we see a natural illustration of a countably infinite set of countable sequences whose union is all the natural numbers (an observation of Cantor).
Rather more surprisingly, the following is true:
Take any sequence of positive numbers which, after the first two terms, satisfies the Fibonacci recurrence. Then this sequence, from some point on, agrees with some row of the table from some point on.
For example, the sequence beginning 2, 1 continues 3, 4, 7, …, and from that point on, agrees with the second row of the table.
So the “special” sequences we defined earlier are not so special after all!
The first two columns are obtained by extrapolating backwards using the Fibonacci recurrence; in other words, we take each entry to be the difference of the two which follow it. Then the following remarkable properties hold:
- The entries in the first column are all the non-negative integers in order. So we can use these entries as “labels” for the sequences.
- The second entry is one more than σ applied to the first, and the third entry (the first “real” entry of the sequence) is one less than σ applied to the second. So we can easily generate a row from its number using the function σ.
These things are not too difficult to prove, but I won’t go through the arguments here.
That’s enough for now …