Finding the Fibonacci Numbers: The Problem

The 1202 mathematics textbook Liber Abaci is arguably one of the most important contributions to the development of the scientific and cultural systems we have in the world today, especially for Western society. Written by Leonardo of Pisa, known colloquially by the name Fibonacci, this text introduced to the Western world important notations and mathematical techniques and ways of writing numbers that had developed in other parts of the world that would, over time, contribute to a cultural and scientific explosion. For example, early in Liber Abaci, Fibonacci writes the following:

“These are the nine figures of the Indians: 9 8 7 6 5 4 3 2 1. With these nine figures, and with this sign 0 which in Arabic is called zephirum, any number can be written, as will be demonstrated.” [1]

This is a profound statement. Up until this point in the Western world, the number system was non-positional and complicated. An X always meant 10 (though of course IX means 9), and there was no other way to use the symbol X. Because each symbol has only one possible meaning, you need more symbols to express larger numbers. But the system Fibonacci is introducing is different. He claims that all numbers can be represented with the symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. This is, of course, the system we use today. Liber Abaci was the book that introduced this way of writing numbers to the Western world. This system makes basic addition, subtraction, and multiplication way, way easier to do (try adding CXIV to CXIII without converting to the modern number system)! This alone makes Liber Abaci ground-breaking in the history of science. I’d highly recommend that any interested reader look more into the many fascinating mathematical developments that occurred in the timeframe of 1200-1500. It is quite likely that I will write about the solution of cubic equations that developed during this time period – I believe this story could be made into an entertaining movie.

However, this is not the story I’d like to tell today. This book also introduced to the world one of the most well-known and popular objects in all of mathematics. Today, we call this object the Fibonacci sequence. The book Liber Abaci, like most math books, contains practice problems that can be used to help its readers master its contents. One of the practice problems in Liber Abaci uses breeding rabbits. We are asked to imagine that we start with one pair of baby rabbits. We suppose that after one month of being alive, a pair of rabbits can reproduce a new pair of rabbits exactly once a month. The question asks how many rabbits there will be after one year of all the rabbits reproducing.

For those of you who are most interested in the application of mathematics to the real world, notice that the birth of the Fibonacci sequence is quite applied. This is a simplified version of how population growth works, and so if you want to understand how populations of living things grow, the first thing you want to understand is this problem. After that, you can add new features – like dying rabbits or food shortages – that make the results more and more realistic. So, although the problem may seem in some ways esoteric, it is most certainly not.

Anyways, back to the problem. How do we solve this? Let’s walk through.

Month 0: We start off with one pair of baby rabbits. They cannot reproduce this month, because they are too young.

Month 0 Total: 1 pair of rabbits. 0 adult pairs, 1 baby pair.

Month 1: We still only have one pair of rabbits. But now these are adult rabbits, so they will have babies next month.

Month 1 Total: 1 pair of rabbits. 1 adult pair, 0 baby pairs.

Month 2: The adult pair has now given birth to a new baby pair. This baby pair won’t give birth to any new rabbits until next month, but the adult pair will now be giving birth to a new pair of baby rabbits every month.

Month 2 Total: 2 pairs of rabbits. 1 adult pair, 1 baby pair.

Month 3: The 1 adult pair from Month 2 gave birth to a new baby pair, and the baby pair from Month 2 grew up into an adult pair.

Month 3 Total: 3 pairs of rabbits. 2 adult pairs, 1 baby pair.

Month 4: As in all the months leading up to this point, every adult pair gives birth to a baby pair, and all baby pairs grow up into new adult pairs.

Month 4 Totals: 5 pairs of rabbits. 3 adult pairs, 2 baby pairs.

We now take a pause to recognize the pattern. As stated in Month 4, there is a systematic way to determine the new numbers every month. What the description in Month 4 tells us is this:

Adult Pairs Next Month = Adult Pairs this Month + Baby Pairs This Month,

Baby Pairs Next Month = Adult Pairs this Month.

To make this all shorter to write, define A_n as the number of adult rabbit pairs after n months, and B_n as the number of baby rabbit pairs after n months (A is short for adult, B is short for baby). Then the previous equations tells us that A_{n+1} = A_n + B_n and that B_{n+1} = A_n. This gives us a systematic way to determine the answer. We know that A_0 = 0, B_0 = 1. Our Month 1 calculation tells us that A_1 = 1, B_1 = 0. Our Month 2 calculation tells us that A_2 = 1, B_2 = 1. We stopped our calculations thus far as Month 4, at which point A_4 = 3, B_4 = 2. The concepts we used to find the equations for A_{n+1} and B_{n+1} now enable us to carry out our work faster. We now find that A_5 = A_4 + B_4 = 3 + 2 = 5 and B_5 = A_4 = 3. There are then 8 total rabbit pairs after 5 months.

Now is a convenient time to introduce the famous sequence that I mentioned briefly to begin this article. The Fibonacci sequence is defined by the list of total numbers of rabbits – 1, 1, 2, 3, 5, 8, etc. We normally define the number of rabbits after n months by the shorthand F_n (the F being short for Fibonacci). Since the total number of rabbits is always A_n + B_n, we can define F_n = A_n + B_n.

Using the new equation F_n = A_n + B_n along with the equations that tell us how to calculate values of A_n and B_n, we can form an equation for calculating values of F_n. We can do this by a simple application of the rules we already know – that A_{n+1} = A_n + B_n and that B_{n+1} = A_n. The first thing that we can notice is that F_n and A_{n+1} are both equal to A_n + B_n, and so F_n = A_{n+1}. Using the same logic, A_n = F_{n-1}, and since B_{n+1} = A_n, we conclude that B_{n+1} = F_{n-1}. Putting everything together, we conclude that

F_{n+1} = A_{n+1} + B_{n+1} = F_n + F_{n-1}.

Now, this formula is interesting. What this equation really says is that to find the next entry in our list (1, 1, 2, 3, 5, 8, etc.), we add together the two most recent items in our list. For example, 3 + 5 = 8. Using this logic, the next item in our list must be 5 + 8 = 13. Using the notation of F_n, the original problem of Fibonacci can be rephrased as finding the value of F_{12}. Now that we have an easy formula, this is a much quicker task so far, we found that F_0 = 1, F_1 = 1, F_2 = 2, F_3 = 3, F_4 = 5, F_5 = 8, F_6 = 13. By continuing the process of adding together the two previous terms, we find that F_7 = 21, F_8 = 34, F_9 = 55, F_{10} = 89, F_{11} = 144, and F_{12} = 233. Thus, as I have framed this problem here, the answer to Fibonacci’s problem is that there will be 233 pairs of rabbits at the end of one year.

Now, I have made a very slight variation from how F_n is normally defined, which I will now “fix” since it will make later posts easier. The equation F_{n+1} = F_n + F_{n-1} is the correct equation, but the “normal starting values” are F_0 = 0, F_1 = 1. This is really just a shift from 1, 1, 2, 3, 5, etc. to 0, 1, 1, 2, 3, 5, etc, so the sequence is really still the same. I do this only because this makes some later pieces of our puzzle a little easier to write down.

Now that I have mentioned the “puzzle” we will be solving, I can now define the puzzle. When given lists of numbers that are determined systematically, it is quite natural to want to know how to determine what all the numbers are. But when you can’t find F_{12} without first finding F_0, F_1, F_2, \dots, F_{10}, and F_{11}, that is quite cumbersome. It would be nice if we could find a faster way – a formula that could skip over all these other values and give us F_{12} straight away.

This, then, is our quest. We are going after a quicker formula to determine the numbers F_n. It turns out there is a formula that does exactly this. The next several posts will provide a step by step mathematical and conceptual story of how we can find it.



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 )

Google photo

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

Connecting to %s

%d bloggers like this: