Fibonacci numbers, 7

I set a question about Fibonacci numbers in the coursework for Mathematical Structures. I was taken to task by John Bray for starting the sequence in the wrong place. He claims that the “official” Fibonacci numbers begin F0 = 0, F1 = 1, and claims the authority of that source of all knowledge and wisdom, Wikipedia.

Nobody doubts that the recurrence relation for the Fibonacci numbers is Fn = Fn−1+Fn−2. The point at issue is the “initial conditions”, of which there appear to be three conventions:

  1. F0 = 0, F1 = 1
  2. F0 = 1, F1 = 1
  3. F0 = 1, F1 = 2

As you will not be surprised to learn, I believe that Fibonacci numbers count things. If you think that Fn is the number of compositions of n made of 1s and 2s, then we have the second convention above; if you think that it is the number of zero-one sequences with no two consecutive ones, then we have the third convention.

John, along with (it seems) many other people, prefers the first convention, which has the remarkable property that gcd(Fn,Fm) = Fgcd(m,n), so that in particular, if m divides n then Fm divides Fn. This is indeed a lovely property, but we are prepared to relax it in other cases; it holds for the q-integers [n]q = (qn−1)/(q−1), and yet the number of points in n-dimensional projective space over a field of q elements is [n+1]q.

The Wikipedia article gives a lovely illustration of a page from Fibonacci’s Liber Abaci which has a table of the Fibonacci numbers F0, … F12. Fibonacci himself used convention 3 above. This is a little odd, because his famous problem about the breeding rabbits seems to fit more naturally with convention 2: you start with a pair of rabbits at the beginning of the year, they don’t breed in the first month but produce one new pair in each succeeding month. If Fn is the number of pairs of rabbits at the end of month n, then we have convention 2, and the number of pairs at the end of the year is 233, not 377 as the Liber Abaci appears to show.

Can anyone throw light on this?

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.

5 Responses to Fibonacci numbers, 7

  1. Wikipedia says that F_0=0 and F_1=1 (convention 1. Notice that the subscripts are different from what you said Wikipedia and John Bray says).

    Another argument for that convention is that Binet’s formula gives this sequence. If you used one of the other conventions, you would need to add -1 or -2 to the exponents, and get a formula with longer description length. But you might not accept this argument, if you think that Fibonacci number are (just) counting things.

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

  3. Pingback: Counting Twisted Loops | TortoiseFugue™

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