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 …

Previous | Next

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , . Bookmark the permalink.

4 Responses to Fibonacci numbers, 2

  1. Pingback: rods to stems to congruents to GOST to complexity | Peter's ruminations

  2. 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.

  3. Pingback: On Fibonacci numbers and the golden ratio « Maximal determinant blog

  4. Pingback: Weekly links for March 25 | God plays dice

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s