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
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (23)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
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 MSC: 11B39 (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)