Most recent change of FibonacciSequence

Edit made on December 05, 2008 by ColinWright at 22:41:09

Deleted text in red / Inserted text in green

WW
HEADERS_END
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.

[[[>50 The closed form of the Fibonacci Sequence can be derived by
using matrices and computing the eigenvalues. That's because we
have the formula

|>> EQN:\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

|>> EQN:\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: EQN:F(n)=\frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}}
where EQN:\phi is the golden ratio. Since EQN:(-\phi)^{-n} EQN:\phi^{\small-n} approaches 0, we can ignore
that term and say that /F(n)/ is the closest integer to EQN:\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.
----
* 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