Fibonacci sequence

Geometric representation of the Fibonacci numbers

The Fibonacci sequence is a recursive sequence, defined by

$a_0=0,\, a_1=1 \quad, a_{i+2}= a_{i+1} + a_{i}.$

The sequence can then be written as

$(a_i)_{i=0}^{\infty} = (0, 1, 1, 2, 3, 5, 8, 13, 21, \cdots).$

Properties

$\lim_{n \to \infty} \frac{a_{n + 1}}{a_n} = \phi$

where $\phi$ is the golden ratio.

$a_n = \frac{\phi^n - (1-\phi)^n}{\sqrt 5 } = \frac{(1+\sqrt 5)^n - (1-\sqrt 5)^n}{ 2^n \sqrt 5 }$

Proof

We are given this recurrence relation,

$F_{n} = F_{n-1} + F_{n-2}$

Which is subject to $F_1=1$ and $F_2=1$. One may form an auxiliary equation in $\lambda$ accordingly and solve for $\lambda$.

$\lambda^2 - \lambda - 1 = 0$

Through the use of the quadratic formula, one will obtain,

$\lambda = \frac{1\pm\sqrt{5}}{2}$

or equivalently

$\lambda = \phi\, \text{or}\,\lambda = 1 - \phi$

So we have,

$F_{n} = C_1(\phi)^n + C_2(1-\phi)^n$

where $C_1$ and $C_2$ are constants to be determined. Substituting the values we have

$1 = C_1\phi + C_2(1-\phi),$

$1 = C_1\phi^2 + C_2(1-\phi)^2.$

Solving for both variables, we obtain,

$C_1 = \frac{1}{\sqrt{5}},$

$C_2 = -\frac{1}{\sqrt{5}}.$

So, one has

$F_n = \frac{1}{\sqrt{5}} \left(\phi^n - [1-\phi]^n\right)$

as required.

$\blacksquare$

Sum

For all integers $n \geq 1$,

$\sum_{t=1}^{n} F_{t} = F_{n+2} - 1.$

Proof

Proposition: given

$F_n$ as defined above,

$\sum_{t=1}^{n} F_{t} = F_{n+2} - 1$$\forall n\in \N$

Let $n=1$,

$\sum_{t=1}^{n} F_{t} = F_{1} = 1 = F_{3} - 1$

Therefore the proposition holds for $n=1$. Assume that the proposition holds for $n=\lambda\in\mathbb{Z}^+$. We may now make use of the inductive step. Let $n=\lambda + 1$.

$\sum_{t=1}^{\lambda+1} F_{t} = \sum_{t=1}^{\lambda} F_{t} + F_{\lambda + 1}$.

We know that

$\sum_{t=1}^{\lambda} F_{t} = F_{\lambda + 2} - 1$

from the assumption that the proposition holds for $n = \lambda$.

So, we have,

$\sum_{t=1}^{\lambda+1} F_{t} = F_{\lambda + 2} + F_{\lambda + 1} - 1$

Using the definition,

$F_{n} = F_{n-1} + F_{n-2}$

one obtains

$\sum_{t=1}^{\lambda+1} F_{t} = F_{\lambda + 3} - 1$

which obeys the proposition

$\sum_{t=1}^{\lambda} F_{t} = F_{\lambda + 2} - 1.$

As the proposition holds for $n=1$, $n = \lambda$ and $n = S(\lambda)$, the proposition holds for all natural numbers.

$\blacksquare$

Binet's Formula

Binet's Formula is a theorem that allows one to determine  $F_n$, where $F_n$ represents the $n^{th}$ Fibonacci Number.

The theorem is as follows:

$F_n= \frac{1}{\sqrt{5}} \cdot \left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right).$

Lucas sequence

The recursive effect from the Fibonacci sequence can also be applied with other starting numbers, like the Lucas numbers, which start with 2 and 1, instead of 0 and 1.

Trivia

• Fibonacci numbers are claimed to be common in nature; for example, the shell of a nautilus being a Fibonacci spiral. However, this has been disputed with the spiral having a ratio measured between 1.24 to 1.43.

Terms

Input	Fibonacci	Lucas
0	0	2
1	1	1
2	1	3
3	2	4
4	3	7
5	5	11
6	8	18
7	13	29
8	21	47
9	34	76
10	55	123
11	89	199
12	144	322
13	233	521
14	377	843
15	610	1364