# derivation of Binet formula

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+\sqrt{5}}{2},\qquad\psi=\frac{1-\sqrt{5}}{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+\sqrt{5}}{2}\right)-u\left(\frac{1-\sqrt{5}}{2}\right)=u\left% (\frac{2\sqrt{5}}{2}\right)=u\sqrt{5}.$

Therefore

 $u=\frac{1}{\sqrt{5}},\qquad v=\frac{-1}{\sqrt{5}}$

and so

 $f_{n}=\frac{\phi^{n}}{\sqrt{5}}-\frac{\psi^{n}}{\sqrt{5}}=\frac{\phi^{n}-\psi^% {n}}{\sqrt{5}}.$
Title derivation of Binet formula DerivationOfBinetFormula 2013-03-22 15:03:50 2013-03-22 15:03:50 drini (3) drini (3) 4 drini (3) Derivation msc 11B39