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

$$\varphi =\frac{1+\sqrt{5}}{2},\psi =\frac{1-\sqrt{5}}{2}$$

so the closed formula for the Fibonacci sequence must be of the form

$$f_n=u{\varphi }^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{\varphi }^0+v{\psi }^0,1=u{\varphi }^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}},v=\frac{-1}{\sqrt{5}}$$

and so

$$f_n=\frac{{\varphi }^n}{\sqrt{5}}-\frac{{\psi }^n}{\sqrt{5}}=\frac{{\varphi }^n-{\psi }^n}{\sqrt{5}}.$$

Title	derivation of Binet formula
Canonical name	DerivationOfBinetFormula
Date of creation	2013-03-22 15:03:50
Last modified on	2013-03-22 15:03:50
Owner	drini (3)
Last modified by	drini (3)
Numerical id	4
Author	drini (3)
Entry type	Derivation
Classification	msc 11B39