Fibonacci Sequence

AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

• F(0)=0
• F(1)=1
• F(n)=F(n-1)+F(n-2)

• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

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

Compare with the Perrin Sequence.

• http://en.wikipedia.org/wiki/Fibonacci_number
• http://mathworld.wolfram.com/FibonacciNumber.html
• http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibnat.html
• http://www.google.com/search?q=fibonacci+sequence