## Fibonacci numbers, 2

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 NFk as a sum of non-consecutive Fibonacci numbers, which is taken care of by that wonderful tool, induction.

For example,

 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 … I count all the things that need to be counted.
This entry was posted in exposition and tagged , . Bookmark the permalink.

### 8 Responses to Fibonacci numbers, 2

1. silver price says:

Fibonacci spiral patterns appear in many plants, such as pinecones, pineapples, and sunflowers. The patterns consist of spirals that curve around a surface in both the ³sinister² form (clockwise) and the ³dexter² form (counterclockwise). The numbers of spirals on a surface are two consecutive numbers in the Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, etc.). For example, Li, Ji, and Cao produced a series of spirals of 3×5, 5×8, 8×13, and 13×21. Because their microstructures were very small, the next series (21×34) would have required more than 700 ‘spherules,’ creating so much stress that the structure would break.

2. Adrian Morgan says:

Hmm. Take a positive integer n. Construct a new number Ϥ(n) as a sum of Fibonacci numbers by the following method. Starting with the least significant figure in the binary representation of n, interpret a 0 as an instruction to skip the least remaining Fibonacci number, and interpret a 1 as an instruction to add the least remaining Fibonacci number and skip the next. For example, the binary representation of 100 is 1100100, which we interpret as [skip 1], [skip 2], [add 3 skip 5], [skip 8], [skip 13], [add 21 skip 34], [add 55 skip 89]. This gives Ϥ(100) = 3 + 21 + 55 = 79.

For each positive integer n, there is a unique positive integer Ϥ(n) and vice versa. The values of Ϥ(n) for the first few n are 1, 2, 4, 3, 6, 7, 12, 5, 9, 10, 17, 11, 19, 20, 33, 8. Writing the inverse function of Ϥ as Ϥ⁻¹, we can express the relationship between Ϥ and σ as σ(n) = Ϥ(2Ϥ⁻¹(n)).

For n = 5, the iteration n→Ϥ(n) has the following period ten loop: 5 → 6 → 7 → 12 → 11 → 17 → 14 → 20 → 16 → 8 → 5. For n = 13, n→Ϥ(n) has the following period fourteen loop: 13 → 19 → 25 → 30 → 54 → 66 → 36 → 24 → 18 → 15 → 33 → 22 → 28 → 32 → 13.

I don’t have a conclusion; I’m just wondering where all this might lead. Also, I haven’t double-checked everything and may well have made errors.

• Adrian Morgan says:

Errata on previous comment: I messed up the iteration from n=13, which probably says more about the state of my disorganised pages of scribbles than anything else.

Extended in both directions, I believe the correct orbit is: …, 10240, 1220, 736, 513, 145, 103, 211, 347, 805, 896, 356, 312, 285, 430, 918, 1536, 322, 180, 194, 125, 375, 1355, 2080, 390, 329, 297, 276, 160, 68, 37, 40, 26, 31, 88, 73, 64, 21, 27, 51, 80, 42, 44, 45, 74, 65, 35, 38, 41, 43, 72, 39, 67, 59, 140, 100, 79, 177, 192, 76, 66, 36, 24, 18, 15, 33, 22, 28, 32, 13, 19, 25, 30, 54, 83, 114, 138, 99, 127, 609, 454, 583, 711, 1321, 1263, 5146, … and it shows no sign of cycling.

Values of Ϥ(n) up to n=63 are: 1, 2, 4, 3, 6, 7, 12, 5, 9, 10, 17, 11, 19, 20, 33, 8, 14, 15, 25, 16, 27, 28, 46, 18, 30, 31, 51, 32, 53, 54, 88, 13, 22, 23, 38, 24, 40, 41, 67, 26, 43, 44, 72, 45, 74, 75, 122, 29, 48, 49, 80, 50, 82, 83, 135, 52, 85, 86, 140, 87, 142, 143, 232, …

• Adrian Morgan says:

Final word on this: I’ve now checked my calculations with a computer, and have uploaded my data as a two-page PDF, which I can always append if I make any more observations. Includes graphs. (I’ve also explored algorithms for incrementing/decrementing, adding/subtracting encoded binary strings by hand, but have not attempted to communicate this.)

I made one error above: Ϥ⁻¹(896) is 413, not 805.

3. Adrian Morgan says:

OK, I’ve done substantially more work on the above and the PDF of my results is now seven pages long and much better written. I hope it’s of interest. The closing remarks contain a link to a G+ post where comments can be posted.

This site uses Akismet to reduce spam. Learn how your comment data is processed.