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:
etc.
Compare with the Perrin Sequence.