|
|
|
|
derivation of Binet formula
|
(Derivation)
|
|
|
The characteristic polynomial for the Fibonacci recurrence $f_n = f_{n-1}+f_{n-2}$ is $$ x^2 = x +1. $$
The solutions of the characteristic equation $x^2-x-1=0$ are $$ \phi=\frac{1+\sqrt5}2,\qquad \psi=\frac{1-\sqrt5}2 $$ so the closed formula for the Fibonacci sequence must be of the form $$ f_n = u\phi^n +v\psi^n $$ for some real numbers $u,v$ . Now we use the boundary conditions of the recurrence, that is, $f_0=0, f_1=1$ , which means we have to solve the system $$ 0=u \phi^0 +v\psi^0, \qquad 1=u\phi^1 + v\psi^1 $$ The first equation simplifies to $u=-v$ and substituting into the second one gives: $$ 1=u\left(\frac{1+\sqrt5}2\right) - u\left(\frac{1-\sqrt5}2\right) = u\left(\frac{2\sqrt{5}}2\right)=u\sqrt{5}. $$
Therefore $$ u=\frac{1}{\sqrt5},\qquad v=\frac{-1}{\sqrt5} $$ and so $$ f_n = \frac{\phi^n}{\sqrt5}- \frac{\psi^n}{\sqrt5}=\frac{\phi^n-\psi^n}{\sqrt5}. $$
|
"derivation of Binet formula" is owned by drini. [ owner history (1) ]
|
|
(view preamble | get metadata)
Cross-references: equation, boundary conditions, real numbers, Fibonacci sequence, formula, closed, characteristic equation, solutions, Fibonacci, characteristic polynomial
This is version 1 of derivation of Binet formula, born on 2005-02-19.
Object id is 6784, canonical name is DerivationOfBinetFormula.
Accessed 3774 times total.
Classification:
| AMS MSC: | 11B39 (Number theory :: Sequences and sets :: Fibonacci and Lucas numbers and polynomials and generalizations) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|