Fibonacci numbers, 1

The only thing we knew for sure about Henry Porter is that his name wasn’t Henry Porter,

said Bob Dylan.

Mathematics is littered with things named after people who didn’t invent them. According to Alan Sokal, the Ising model was invented by Ising’s thesis adviser Lenz, and its generalisation the Potts model was invented by Potts’ thesis adviser Domb. (As Sokal points out, this is a reversal of the more common academic practice where the student’s discovery is named after the adviser.) There is also the (probably apocryphal) story that Euler named Pell’s equation because he knew that some English mathematician had worked on it, and thought it might have been Pell. (The equation was already more than a thousand years old at that point.)

Anyway, it will be no surprise to learn that Fibonacci didn’t invent the Fibonacci numbers. In his book Liber Abaci, he posed the problem of calculating the twelfth Fibonacci number, in terms of a charming if unreal problem about the breeding of rabbits; but he wasn’t interested in these numbers particularly, or indeed in breeding rabbits. His book was propoganda for the use of the Indian numerals (which have also been misnamed as Arabic numerals) in European commerce, and he simply wanted to show how quickly the number could be computed using these numerals rather than any competing method.

But I want to talk about a different mystery here. Different people start the sequence in different places, so that I cannot simply say “the twelfth Fibonacci number F12” as the answer to the rabbit problem.

Everyone agrees on the growth law, or recursion, for the Fibonacci numbers. Each one after the first two is the sum of the two which precede it. (I’ll call this the Fibonacci recurrence.) With this rule, it is clear that if I tell you what the first two numbers are, you can calculate the third, then the fourth, then … But you do need to know the first two numbers, and there are different conventions. Some people take F0 = F1 = 1, so that F2 = 2, F3 = 3, F4 = 5, and so on. Others, however, prefer F0 = 1, F1 = 2, so that F2 = 3, F3 = 5, et cetera.

There are two natural problems to which the Fibonacci numbers provide the answer; we will see that they do naturally give rise to these two conventions. Each is a counting problem; as you know, I believe that we have numbers in order to count the things that matter!

The first and older problem is:

In how many ways can the number n be expressed as an ordered sum (or composition) of 1s and 2s?

This problem had been discussed by the Sanskrit grammarian Virahanka in the 6th century, in connection with Sanskrit poetry. Since I know nothing about Sanskrit poetry, you will have to forgive the fact that this is second-hand. A vowel in Sanskrit can be long (guru) or short (laghu). If we assume that a long vowel is twice as long as a short vowel, in how many ways can we make a line of poetry of length n out of long and short vowels? For example, the lines of length 4 are GG, LLG, LGL, GLL, LLLL, where G and L denote guru and laghu respectively. It is clear that this problem is exactly the one just stated. A more down-to-earth way of putting it: I am standing at the bottom of a staircase with n steps; at one stride, I can ascend either one or two steps. In how many ways can I reach the top?

To see that the Fibonacci recurrence holds, suppose that n is at least two, and watch me take the first stride. I can ascend either one step (in which case there are n−1 to go) or two steps (in which case n−2 remain). Since there is no overlap and all cases are covered, I add the numbers for n−1 and for n−2 to obtain the number for n.

It is clear that there is only one way of walking up one step. There is also, though perhaps this is rather more puzzling, one way of walking up no steps at all; just do nothing! So the 0th and 1st terms of the sequence are both 1.

The other standard Fibonacci problem is:

How many sequences of length n of As and Bs are there which have no two consecutive Bs?

For n = 3, there are five sequences: AAA, AAB, ABA, BAA and BAB; the three sequences ABB, BBA and BBB are forbidden.

To see that the Fibonacci recurrence holds, look at the sequences of length n, and divide them into two heaps: those beginning with A, and those beginning with B. Each sequence in the first heap is obtained by starting with A and appending any legal sequence of length n−1. For sequences in the second heap, the B must be followed by an A, and then any legal sequence of length n−2 can safely be appended. Again we have covered everything without overlap.

There is only one sequence of length 0, namely the empty sequence; and there are two sequences of length 1, namely A and B.

So these two basic problems do indeed give us the two conventions for the Fibonacci numbers.

It is natural to look for a correspondence between the two counting problems to show that the answers are the same apart from the shift, that is, that the number of compositions of n is equal to the number of sequences of length n−1 without consecutive Bs.

This can be done. Write a sequence of n ones. There are n−1 gaps between the ones. Imagine that we put “barriers” in some of the gaps. Then counting the ones between the barriers gives a composition of n. To ensure that the summands are 1 or 2, we must put at least one barrier in any two consecutive spaces; in other words, two consecutive “non-barriers” are forbidden. Now translate by putting A for a barrier and B for the absence of one to get a sequence with no two consecutive Bs. The procedure reverses.

To illustrate, here are the five compositions of 4 made up of ones and twos, with the corresponding barriers and sequences.

2+2 2+1+1 1+2+1 1+1+2 1+1+1+1
1 1|1 1 1 1|1|1 1|1 1|1 1|1|1 1 1|1|1|1

Incidentally, if we drop the restrictions that gave us Fibonacci numbers, we see that the total number of compositions of n is equal to the total number of sequences of As and Bs of length n−1, which is of course 2n−1. The “forbidden” sequences ABB, BBA and BBB correspond to the compositions 1+3, 3+1 and 4 respectively.

How do Fibonacci’s rabbits fit in?

The problem is: at the start of the year I acquire a new-born pair of rabbits. A pair does not breed in its first month, but after that it produces one pair of rabbits every month. How many pairs do I have at the end of a year?

At the end of month n (for n ≥ 2), I have all the pairs that were alive at the end of the preceding month, together with new pairs born to the rabbits who are at least two months old (that is, those that were alive at the end of the month before that). So the number of pairs after month n is the sum of the numbers after months n−1 and n−2. Thus, the Fibonacci recurrence holds. The number of pairs after 0 months, and the number after 1 month, are both equal to 1. So the sequence has the same initial conditions as the sequence counting the compositions of n using 1s and 2s, and the values agree for all n. Tradition suggests that we define this as the Fibonacci sequence, with nth term Fn. The sequence begins

F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5, …

and grows according to the recurrence Fn = Fn−1+Fn−2. Completing Fibonacci’s exercise we see that F12 = 233.

What about a direct proof of this? I will cheat slightly and show that the number of pairs of rabbits at the start of month n is equal to the number of strings of As and Bs of length n−1 with no two consecutive Bs. For this purpose, I will give every pair of rabbits a pedigree, consisting of a string of length n+1, formed as follows (think B=”born”, A=”alive”):

  • A new-born pair of rabbits is given a pedigree which consists of their parents’ pedigree in the preceding month followed by B;
  • After that, at the start of each month we add A to the pedigree.

A pedigree cannot contain two successive Bs, since a pair of rabbits do not have offspring in the first month. Every pair receives a different pedigree. Does every admissible string occur? No, because the pedigree of the ancestral pair begins BA, and so then does every pedigree. But it is easy to see that deleting the initial BA we obtain all admissible strings.

In later posts in this sequence I will tell you more about Fibonacci numbers.



About Peter Cameron

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

5 Responses to Fibonacci numbers, 1

  1. Olof Sisask says:

    I like the `walking up the stairs’ phrasing of the problem — it relates to something many people have done and seems a fairly natural thing to wonder. I think it also provides a natural way to think about the correspondence with the A-B problem: simply drop As on any steps that you actually step on, and drop Bs on any steps you don’t step on. Since you can’t skip more than one step, there are no two consecutive Bs.

  2. S says:

    Among other good reasons to adopt the convention of starting with F_0 = 0, the clincher for me is this: with this convention, we have the properties that F_m | F_n \iff m | n and indeed that F_{\mbox{gcd}(m,n)} = \mbox{gcd}(F_m, F_n). These get really messy with the other off-by-one convention.

    I like the ‘ascending the staircase’ formulation too!

    • That is yet a different convention. It has the nice consequence that the 12th Fibonacci number turns out to be 144 (which I think, from memory, was Fibonacci’s answer, and also happens to be 122).

      I thought for some time about whether or not to include it, and in the end decided not to. It is a convention honoured in the breach. For example, the numbers Θn=(qn−1)/(q−1) (for fixed q) have the property that, for positive integers q, Θm divides Θn if and only if m divides n. And yet, if you ask any geometer, you will be told that Θn is the number of points in (n−1)-dimensional projective space!

      We are, I’m afraid, stuck with some of these shifts. I will explain another reason for the convention I have adopted in the next post in this series.

  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: Logo

You are commenting using your 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