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 F_{0} = 0, F_{1} = 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 F_{n} = F_{n−1}+F_{n−2}. The point at issue is the “initial conditions”, of which there appear to be three conventions:
- F_{0} = 0, F_{1} = 1
- F_{0} = 1, F_{1} = 1
- F_{0} = 1, F_{1} = 2
As you will not be surprised to learn, I believe that Fibonacci numbers count things. If you think that F_{n} 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(F_{n},F_{m}) = F_{gcd(m,n)}, so that in particular, if m divides n then F_{m} divides F_{n}. This is indeed a lovely property, but we are prepared to relax it in other cases; it holds for the q-integers [n]_{q} = (q^{n}−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 F_{0}, … F_{12}. 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 F_{n} 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?
OEIS Wiki • Fibonacci Numbers
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.
Misprint corrected – sorry.
Pingback: Weekly links for March 25 | God plays dice
Pingback: Counting Twisted Loops | TortoiseFugue™