0x0011 - Fibonacci sequence

The Fibonacci sequence in mathematics is the following sequence of numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 …

Representation

By definition, the first two terms are 0 and 1, and each of the terms following them are the sum of two previous terms. So, if we say Fn is the nth term in the Fibonacci sequence, then we can express the sequence recursively as:

Fn = Fn-1 + Fn-2

seeded with F0 = 0 and F1 = 1.

Negative Indices

The sequence can also be extended to negative indices. Rearranging the terms in the equation above, we have

Fn-2 = Fn – Fn-1

Substituting values of n as 1, 0, -1, -2, -3, … we get:

F-1 = F1 – F0 = 1 – 0 = 1

F-2 = F0 – F-1 = 0 – 1 = -1

F-3 = F-1 – F-2 = 1 – (-1) = 2

F-4 = F-2 – F-3 = -1 – 2 = -3

F-5 = F-3 – F-4 = 2 – (-3) = 5

and so on. Looking at the terms of negative indices, we can get the formula

F-n = (-1)n+1 Fn

The sequence now looks like:

… 13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, …

Relation to Golden Ratio

The relation of Fibonacci terms with the Golden Ratio is already discussed in this post. In brief, the nth term of the Fibonacci sequence is given by Binet’s Formula,: $F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5}$

where

$\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803,39887\dots,$

is the Golden Ratio, and

$\psi = \frac{1 - \sqrt{5}}{2} = 1 - \varphi = - {1 \over \varphi}.$

Finding the nth Fibonacci term

Since: $\frac{|\psi|^n}{\sqrt 5} < \frac{1}{2}$
for all n ≥ 0, the number F**n is the closest integer to: $\frac{\varphi^n}{\sqrt 5}, .$

Therefore it can be found by rounding off the term above. In terms of the floor function:

$F_n=\bigg\lfloor\frac{\varphi^n}{\sqrt 5} + \frac{1}{2}\bigg\rfloor,\ n \geq 0.$

For negative n, use ψ instead of φ in the equation above.

Finding index of a given Fibonacci term

If we already know that the number F > 1 is a Fibonacci number, we can determine its index within the sequence by: $n(F) = \bigg\lfloor \log_\varphi \left(F\cdot\sqrt{5} + \frac{1}{2}\right) \bigg\rfloor$

Recognizing Fibonacci Terms

In 1972, Gessel gave a surprisingly simple test:

N is a Fibonacci number if and only if 5N2 + 4or 5N2 – 4 is a square number.

For instance,

3 is a Fibonacci term since 5×32+4 is 49 which is 72
5 is a Fibonacci term since 5×52–4 is 121 which is 112
4 is not a Fibonacci term since neither 5×42+4 = 84 nor 5×42–4 = 76 are perfect squares.

Suppose we are given a Fibonacci term N and we have to find its index. Using approximation of Binet’s Formula and taking logarithms on both sides, we have

log N = n log(φ) – log(5)/2

which gives

n = ( log N + log(5)/2 ) / log(φ)**

So if we take N as 5, then n will evaluate to 6, when ceiled.