PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] derivation of Binet formula (Derivation)

The characteristic polynomial for the Fibonacci recurrence $f_n = f_{n-1}+f_{n-2}$ is

\begin{displaymath} x^2 = x +1. \end{displaymath}

The solutions of the characteristic equation $x^2-x-1=0$ are

\begin{displaymath} \phi=\frac{1+\sqrt5}2,\qquad \psi=\frac{1-\sqrt5}2 \end{displaymath}

so the closed formula for the Fibonacci sequence must be of the form
\begin{displaymath} f_n = u\phi^n +v\psi^n \end{displaymath}

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
\begin{displaymath} 0=u \phi^0 +v\psi^0, \qquad 1=u\phi^1 + v\psi^1 \end{displaymath}

The first equation simplifies to $u=-v$ and substituting into the second one gives:
\begin{displaymath} 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}. \end{displaymath}

Therefore

\begin{displaymath} u=\frac{1}{\sqrt5},\qquad v=\frac{-1}{\sqrt5} \end{displaymath}

and so
\begin{displaymath} f_n = \frac{\phi^n}{\sqrt5}- \frac{\psi^n}{\sqrt5}=\frac{\phi^n-\psi^n}{\sqrt5}. \end{displaymath}



"derivation of Binet formula" is owned by drini. [ owner history (1) ]
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: equation, boundary conditions, real numbers, Fibonacci sequence, 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 3166 times total.

Classification:
AMS MSC11B39 (Number theory :: Sequences and sets :: Fibonacci and Lucas numbers and polynomials and generalizations)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)