## FANDOM

1,020 Pages

The Fibonacci sequence is a recursive sequence, defined as

$a_0=0, a_1=1$
$\{a_i\}_{k=0}^{\infty} = a_{i-1} + a_{i-2} = 0, 1, 1, 2, 3, 5, 8, 13, 21, ...$

## Properties

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

$\phi$ is equal to 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+\sqrt{5}}{2}$ or $\lambda = \frac{1-\sqrt{5}}{2}$

Or otherwise,

$\lambda = \phi$ or $\lambda = \overline{\phi}$

So we have,

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

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

$1 = C_1\phi + C_2\overline{\phi}$
$1 = C_1\phi^2 + C_2\overline{\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 - [\overline{\phi}]^n\right)$

As required $\blacksquare$

## Sum

For all integers $n$ greater than or equal to $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 \mathbb{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$. 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$

## 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

1. Peterson, Ivars (April 1, 2005). "Sea Shell Spirals". Science News.