Applications of the Fibonacci sequence

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

How many ways are there to tile a $2 \times n$ grid with $1 \times 2$ dominos?

This problem can be solved using Fibonacci numbers. Let S_n 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 S_n = S_n-1 + S_n-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 S₁ = 1 and S₂ = 2. Therefore, the number of tilings is precisely the Fibonacci sequence.

Answer 6

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

Answer 7

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.

Answer 8

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/

Answer 9

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

Answer 10

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.

Answer 11

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

Answer 12

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."

Answer 13

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.

See https://math.stackexchange.com/questions/789804/how-many-distinct-ways-to-climb-stairs-in-1-or-2-steps-at-a-time.

Answer 14

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

Answer 15

$$\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.

Answer 16

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

$$\forall n \gt 1 \in \mathbb N, F_{n+1} \ne \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

Answer 17

Fibonacci numbers:

I. OK, to know that the number of the patterns in a flower is a Fibonnacci number might be not useful for the first moment ( until you decide to create flowers as animator for example). Same for topics like the Fibonacci spiral.

II. If you want to teach (young) childrens to combine creativity with practice - the Fibonacci numbers are a great start (without explaning what are fractions).

The practice is explained below.

---

Golden ratio:

I. Let's say you want become a Designer- look at some solutions from your life:

• A piece of A4 paper: 297mm $\times $ 210mm $\rightarrow\frac{297mm}{210mm}\approx1.414$
• Same applications for books
• Display resolutions is a important topic - and totally if somebody creating a PC game in Pixel art graphics, like in a primary 640 pixels $\times$ 360 pixels window (the ratio: $1.(7)$) scaled by 2 for example

Proportions close to the golden ratio looking nice for the eye

II. Not away are artists drawing (or modeling) for example humans- golden ratio body proportions

III. Big topic in general designs (homes, street signs and more): Mettalic mean (Could not found: The japanese ratio is $\sqrt2:1$)

That's actually only the tip of the iceberg .

Answer 18

They're a much easier way to evaluate the function

$f(x) = \dfrac{\varphi^x -(-\varphi)^x}{\sqrt{5}}$

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