# Applications of the Fibonacci sequence

The Fibonacci sequence is very well known, and is often explained with a story about how many rabbits there are after $n$ generations if they each produce a new pair every generation. Is there any other reason you would care about the Fibonacci sequence?

-
Population growth of rabbits! I can't remember how many times I was told that. But seriously, it's not a very good model. –  Noldorin Jul 22 '10 at 8:05
It's a better model for honey bees than rabbits: johndcook.com/blog/2008/02/15/honeybee-geneology –  John D. Cook Jul 28 '10 at 22:58

Perhaps it's not an entirely practical application, but Fibonacci numbers can be used to convert from miles to kilometers and vice versa:

Take two consecutive Fibonacci numbers, for example 5 and 8. And you're done converting. No kidding – there are 8 kilometers in 5 miles. To convert back just read the result from the other end - there are 5 miles in 8 km!

But why does it work?

Fibonacci numbers have a property that the ratio of two consecutive numbers tends to the Golden ratio as numbers get bigger and bigger. The Golden ratio is a number and it happens to be approximately 1.618.

Coincidentally, there are 1.609 kilometers in a mile, which is within 0.5% of the Golden ratio.

-
This is more useful if you also consider sums of Fibonacci numbers: 18 mi=5 mi + 13 mi = 8 km + 21 km = 29 km. –  Larry Wang Jul 22 '10 at 9:57
Also within 0.009 kilometers-per-mile is 8/5, which is much easier to do in your head :) –  BlueRaja - Danny Pflughoeft Jul 29 '10 at 17:18

Suppose you're writing a computer program to search a sorted array for a particular value. Usually the best method to use is a binary search. But binary search assumes it's the same cost to read from anywhere in the array. If it costs something to move from one array element to another, and the cost is proportional to how many array elements you need to skip over to get from one element you read to the next, then Fibonacci search works better. This can apply to situations like searching through arrays that don't fit entirely in your computer's cache so it's generally cheaper to read nearby elements that distant ones.

-

Consecutive Fibonacci numbers are the worst-case (maximum number of steps) numbers for Euclid's gcd algorithm.

-

Yep, the solution by Matiyasevich to Hilbert's tenth problem relies heavily on showing exponentiation is Diophantine. In other words, the relation R given by $R(x,y,z)$ if and only if $x^y = z$ can be expressed by a polynomial equation $T(x,y,z,w)=0$, such that $R(x,y,z)$ holds if and only if $T(x,y,z,w)=0$ has a solution with $w$ integral. This is a very difficult and technical result, as well as rather counterintuitive.

Recall that the Fibonacci numbers grow essentially exponentially. One of the lemmas in showing that exponentiation is Diophantine is to show that the Fibonacci sequence (and its variants) are Diophantine. See the book by Matiyasevich on Hilbert's 10th problem.

-

it pops up every now and then. For example, positions (F2n, F2n+1) are winning ones in Wythoff's Game.

-

How many ways are there to tile a 2 x n grid with 1 x 2 dominos?

This problem can be solved using Fibonacci numbers. Let Sn be the number of valid tilings of the 2 x n grid. Each such tiling has either a vertical 1 x 2 domino or two horizontal dominos on the right. Therefore, each tiling of a 2 x (n-1) grid or a 2 x (n-2) grid generates a tiling of the 2 x n grid, and hence we have a recurrence relation Sn = Sn-1 + Sn-2. This is precisely the recurrence relation of the Fibonacci numbers. Checking our base cases, we see that there is one way to tile a 1 x 2 grid and two ways to tile a 2 x 2 grid, so S1 = 1 and S2 = 2. Therefore, the number of tilings is precisely the Fibonacci sequence.

-

It isn't exactly an application as such, but the upper bound of the size of a subtree in a Fibonacci heap whose root is a node with degree $k$ is $F_{k+2}$ where $F_n$ is the $n^{th}$ Fibonacci number.

-
ah you beat me to it! –  Jan Gorzny Jul 21 '10 at 20:57

They appear in pattern formation, for instance in the numbers of petals on a plant, the segements on a pineapple or pinecone, and the structure of nautilus shells.

http://library.thinkquest.org/27890/applications5.html

http://www.popmath.org.uk/rpamaths/rpampages/sunflower.html

http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/

-
Apparently, this is mostly an urban legend. See this for more: sciencenews.org/view/generic/id/6030/title/Sea_Shell_Spirals –  Tomer Vromen Jul 22 '10 at 10:35

They're useful in determining the amortized run time of the appropriately named Fibonacci Heap in computer science.

-

Here's an example of Fibonacci numbers applied to numerical integration.

-

It is useful when making estimates (for examples for programming tasks) as

$\forall n \gt 1 \in \mathbb N, F_{n+1} \ne \large\frac{F_{n+2} + F_n}{2}$

and therefore it discourages bad practices like assuming that two equal-sized tasks necessarily take twice as much as one of them (it's false because the larger the scope, the less accurate the estimate).

Example

-

They are sometimes used or occur in financial applications, e.g. Elliot Wave Theory. This seems more like magic than math to me, but I am not a trader.

-

Here's a humorous application of Fibonacci numbers to breastfeeding twins. Even though the post is somewhat of a joke, it makes a serious point about what are called "almost periodic functions."

-

If you have N stairs and can take 1 or 2 of them at each of your steps, the number of different ways to climb to the top is the N-th number in the Fibonacci sequence. This is a "hard" problem on the CodeEval programming site.

-

I will attempt a heuristic answer. When approximating the duration of a relatively short task, if this duration is not obvious, we tend to divide it in at least in 2 sub-tasks that are more manageable. As the duration of two sub-tasks increases, we would tend to continue their fragmenting. However, the total time it would take to address subdivided tasks needs a correction as their duration increases: the sum of the times to deal with every task separately is not equal to the time of doing the tasks consecutively. There seems to be a natural geometrical progression of the time needed to do similar tasks consecutively, as opposed to doing them separately. Think manual activities that need preparation of tools. Think care for 1, 2, 3 or 5 children. In the case of manual labor, tools are only prepared for the first task. In the case of children, as they grow they begin to take care of each other. Stefan N. Maier, PMP

-

$$\lim \limits_{n \to \infty} {D_2(n) \over D_2'(n)}=\lim \limits_{n \to \infty} {F_{n+1} \over F_n} = {1+\sqrt 5 \over 2} = \phi$$ where $D_2(n)$ and $D_2'(n)$ are the partition functions occuring in the Rogers-Ramanujan indentities and $F_n$ is the $n$th Fibonacci number.

-

They're a much easier way to evaluate the function

$f(x) = \large\frac{ø^x -(-ø)^x}{\sqrt{5}}$

by hand, where ø is the golden ratio and $x$ is an integer :)

-