The Fibonacci sequence is a recursive sequence, defined by

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

The sequence can then be written as

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

Properties

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

where ${\displaystyle \phi}$ is the golden ratio.

${\displaystyle 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,

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

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

${\displaystyle \lambda^2 - \lambda - 1 = 0}$

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

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

or equivalently

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

So we have,

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

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

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

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

Solving for both variables, we obtain,

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

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

So, one has

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

as required.

${\displaystyle \blacksquare }$

Sum

For all integers ${\displaystyle n \geq 1}$,

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

Proof

Proposition: given

${\displaystyle F_n}$ as defined above,

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

Let ${\displaystyle n=1}$,

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

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

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

We know that

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

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

So, we have,

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

Using the definition,

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

one obtains

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

which obeys the proposition

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

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

${\displaystyle \blacksquare }$

Binet's Formula

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

The theorem is as follows:

${\displaystyle 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.^[1]

References

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