## Fibonacci Numbers

Note: If your WWW browser cannot display special symbols, like ² or 2 or ø, then click here for the alternative Fibonacci Numbers page.

Fibonacci numbers (named after the 13th Century mathematician, Leonardo of Pisa, also called Leonardo Fibonacci or just Fibonacci) are the elements of the Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 . . .

Sometimes this sequence is given as 0, 1, 1, 2, 3, 5 . . . (0 becomes the 0th element of the sequence). Each number is the sum of the two previous numbers. There are other Fibonacci sequences, starting with other numbers:

3, 10, 13, 23, 36, 59 . . .

These are sequences of Lucas numbers, which are a kind of generalized version of Fibonacci numbers. Often, the sequence beginning with 1, 1 is the only one named after Fibonacci. And that sequence is considered a special case of Lucas numbers.

Fibonacci numbers are closely related to phi (ø), the Golden Ratio 1/2+sqr(5)/2 (where sqr() is the square root function). The ratio of consecutive Fibonacci numbers gets closer and closer to phi, as the number of elements in the sequence gets larger. This leads (fairly directly) to the following series:

phi=1+1/1·1-1/1·2+1/2·3-1/3·5+1/5·8-1/8·13+...

Notice the alternating signs. Each denominator is the product of two consecutive Fibonacci numbers. Where did I get this series? I deduced it from the fact that the ratio of consecutive Fibonacci numbers approaches the golden ratio, as the numbers get larger. The sequence of consecutive Fibonacci numbers is 1/1, 2/1, 3/2, 5/3, 8/5, 13/8,... We get the second element of this sequence with this series: 1+1/1·1. The third element is 1+1/1·1-1/1·2. The fourth is 1+1/1·1-1/1·2+1/2·3, and so on. This series was known long before I discovered it.

The Fibonacci numbers are related to exponential growth (see the rabbits in addendum #1, below). And they are supposedly commonly found in nature. Botanists have said that many plants tend to have a Fibonacci number of petals and leaves. The numbers of a secondary Fibonacci (Lucas) sequence 1, 3, 4, 7, 11 are apparently not quite as common.

Since the ratio of consecutive Fibonacci numbers gets closer and closer to phi, it follows that if x is a Fibonacci number then the next few Fibonacci numbers are approximately:

x, øx, ø2x, ø3x, . . .

Well, if x is one of the first Fibonacci numbers, like 1, then the whole sequence is approximately:

ø0, ø1, ø2, ø3, ...

We can produce integers from these irrational numbers with the round() function (we just round each fraction to the nearest integer):

round(ø0), round(ø1), round(ø2), round(ø3), ...

Let's look at that sequence (with the Fibonacci sequence to compare):

1, 2, 3, 4, 7, 11, 18, 29, 47, 76, 123 . . .

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 . . .

It is a rough fit. The first sequence is an alternate Fibonacci sequence (each element is the sum of the two previous elements) except that the fourth element 4 is not 2+3. I suspect that other larger members of the sequence will also be one off. By the way, we could have started with round(ø-1) which is 1 or round(ø-2) which is 0. Anyway, a power of phi gives a reasonable approximation to any given Fibonacci number. And we can guess that the ratio of consecutive terms of other Fibonacci sequences (ones starting with other numbers) also get close to phi. And we see how the Fibonacci sequence is related to exponential growth.

The following seems to be a perfect fit for the nth Fibonacci number:

Fn=round(øn/sqr(5))

Here is how I derived this formula:

ø2=ø+1=F2ø+F1
ø3=2ø+1=F3ø+F2
ø4=3ø+2=F4ø+F3
ø5=5ø+3=F5ø+F4
. . .
øn=Fnø+Fn-1 (this can be proven)
øn/Fn=Fnø/Fn+Fn-1/Fn
øn/Fn=ø+Fn-1/Fn
lim øn/Fn=ø+lim Fn-1/Fn [Here I use "lim" as short for "the limit as n approaches infinity"]
lim øn/Fn=ø+1/ø=(ø2+1)/ø=(ø+2)/ø=sqr(5)
lim øn/sqr(5)=lim Fn
Fnn/sqr(5) approximately

The round() function should give us an exact fit, forever. Without the round() function, the error is about .001 for the 12th Fibonacci number. And, according to the derivation above, the error should get smaller as n gets larger, as it is all based on the ratio of successive Fibonacci numbers approaching phi. Although I discovered this formula on my own today, it has been known before. See Limits.

In the game of bridge, the amount of pieces of information which can be passed on using what are called Relay Bids, is always a Fibonacci number. Let's say that a partnership has a certain amount of bidding space (between 1C and 2NT, for example). Opening bidder bids 1C. In their bidding system, that is a "relay bid" one that passes no information about clubs, but rather is a show of strength and asks partner to pass information about his/her hand, in coded form. Below 2NT, partner can pass on 9 different kinds of information with his/her next bid, maybe showing how strong his/her hand is. The 1C bidder may then bid the next cheapest bid, as another relay asking for more information. Here, I have marked the relay bids with (r):

 opener responder opener responder opener responder opener responder 1C (r) 1D 1H (r) 1S 1NT (r) 2C 2D (r) 2H 2S 2NT 2D 2H (r) 2S 2NT 2H 2S 2NT 1NT 2C (r) 2D 2H (r) 2S 2NT 2H 2S 2NT 2C 2D (r) 2H 2S 2NT 2D 2H (r) 2S 2NT 2H 2S 2NT 1H 1S (r) 1NT 2C (r) 2D 2H (r) 2S 2NT 2H 2S 2NT 2C 2D (r) 2H 2S 2NT 2D 2H (r) 2S 2NT 2H 2S 2NT 1S 1NT (r) 2C 2D (r) 2H 2S 2NT 2D 2H (r) 2S 2NT 2H 2S 2NT 1NT 2C (r) 2D 2H (r) 2S 2NT 2H 2S 2NT 2C 2D (r) 2H 2S 2NT 2D 2H (r) 2S 2NT 2H 2S 2NT

Here we can pass 55 items of information in the small bidding space between 1C and 2NT. In reality, a relay bidder (the 1C bidder above) will often not relay (bid the cheapest bid, asking for information) unless he is fairly sure of making game (3NT or 4H or 4S). This bidding space (between 1C and 3NT) would allow 610 pieces of information to be passed. Responder could describe his/her strength to within two or three high card points, his/her exact distribution (how many cards he/she has in each suit), and in which suits he/she has aces, kings, queens, and maybe jacks. The opponents get this information, as well; but often they can make little use of it.

Relay bidding tends to be very slow. And it is mostly illegal in the U.S., except in certain events.

If you were surprised that the ratio of consecutive Fibonacci numbers tends toward the golden ratio, consider this sequence (where ø is the golden ratio):

1, ø, ø+1, 2ø+1, 3ø+2, 5ø+3, . . .

This is a Fibonacci sequence, except that only one of the terms is an integer. What is the ratio of any two consecutive terms here? There are strong clues in my Golden Ratio article. If you look at addendum #5, in that article, you will see that the above sequence can be written as:

ø0, ø1, ø2, ø3, ø4, ø5, ...

And the ratio of any two consecutive terms is exactly the golden ratio.

Now let's consider hypothetical rabbits. Let's say we start with two rabbits. After a time, they produce two new rabbits. Then after a time, these four rabbits (ignoring the laws against incest) produce four more rabbits, etc. The number of rabbits at any given time is the sequence 2, 4, 8, 16, 32, ... (or 21, 22, 23, 24, 25, ...). This is called exponential growth. Now let's say that after our rabbits are born, they are too young to produce more rabbits right away. They have to skip a time period before they start producing pairs of rabbits. Here is a diagram:

As you can see, the number of pairs, as time goes on, is the Fibonacci sequence. These rabbits are the famous Fibonacci Rabbits. You can see that this sequence is related to exponential growth. This sequence grows somewhat slower than the doubling shown above. In fact, instead of 21, 22, 23, 24, 25, ..., we can approximate our Fibonacci rabbit population with this series (as we saw above): ø0, ø1, ø2, ø3, ø4, ø5, ... And that is exponential growth.

It may be that theorizing about these rabbits is how Fibonacci came up with the concept of Fibonacci numbers.

In my search for an exact formula for the nth Fibonacci number, I overlooked this simple formula:

F(n) = (øn-(-ø)-n)/sqr(5)

This seems to be exact for all n.

I forgot to tell you what the sum of the first n Fibonacci numbers is. But first, what is the sum of two consecutive Fibonacci numbers? If you said, "I don't know," then you must have been sleeping. Back at the top of this article, I said, "Each number is the sum of the two previous numbers." So the sum of two consecutive Fibonacci numbers is the next Fibonacci number. You just didn't know that I was going to ask an easy question. Anyway, the sum of the first n Fibonacci numbers is:

F1+F2+F3+...+Fn = Fn+2-1