# Fibonacci Sequence

The Fibonacci Sequence is obtained by starting with 0 and 1, then getting each successive term by adding the two previous terms.
• F(0)=0
• F(1)=1
• F(n)=F(n-1)+F(n-2)
This gives:
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Ratios of successive terms approach the golden ratio.

 The closed form of the Fibonacci Sequence can be derived by using matrices and computing the eigenvalues. That's because we have the formula $\left[\begin{matrix}F_n\\F_{n+1}\end{matrix}\right]=\left[\begin{matrix}0&1\\1&1\end{matrix}\right]\left[\begin{matrix}F_{n-1}\\F_n\end{matrix}\right]$ That means $\left[\begin{matrix}F_n\\F_{n+1}\end{matrix}\right]=\left[\begin{matrix}0&1\\1&1\end{matrix}\right]^n\left[\begin{matrix}0\\1\end{matrix}\right]$ and so if only we could compute powers rapidly and easily, then we could compute the Fibonacci Sequence. But that's what eigenvectors and eigenvalues do for us.
Closed form: $F(n)=\frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}}$ where $\phi$ is the golden ratio. Since $\phi^{\small-n}$ approaches 0, we can ignore that term and say that F(n) is the closest integer to $\phi^n/\sqrt{5}$

The Fibonacci sequence turns up in all sorts of places in nature:

• Number of spirals on a
• pine cone
• pineapple
• sunflower centre
etc.

Compare with the Perrin Sequence.