## Binet’s Formula

You will encounter a large number of formulas in your life, and quite many of them just seem to come out of the blue. That’s fortunately quite false, despite it being not always easy to retrace the formulas’ authors’ steps. One that appears as suspicious as it seems magic, is Binet’s Fibonacci Number formula:

$\displaystyle F_n=\frac{\phi^n-(1-\phi)^n}{\sqrt{5}}$,

where

$\displaystyle\phi=\frac{1+\sqrt{5}}{2}$

is the golden number.

But it’s not quite out of nowhere, and, if you know how to solve recurrences using the characteristic equation, it’s in fact quite straightforward. Let’s see how.

The Fibonacci numbers are given by the recurrence relation

$F_n=F_{n-1}+F_{n-2}$,

which is a simple, linear, homogeneous recurrence. Since it’s a linear homogeneous recurrence, there exist a function

$F_n=c_1r_1^n+c_2r_2^n$,

for which we must find $c_1$, $c_2$, $r_1$ and $r_2$.

First, we must make the recurrence take the form

$F_n-F_{n-1}-F_{n-2}=0$.

(Here, nothing special, we just moved terms around to make one size equal to zero.). To this homogeneous recurrence corresponds the characteristic equation

$x^2-x-1=0$,

whose roots we must find. Unfortunately, it is an irreducible polynomial, and we will resort to the quadratic equation to find its roots. Let’s recall that the quadratic polynomial equation:

$ax^2+bx+c=0$

has roots given by

$\displaystyle\frac{-b\pm\sqrt{b^2-4ac}}{2a}$.

Using this with $a=1$, $b=c=-1$, we find

$\displaystyle r=\frac{1\pm\sqrt{5}}{2}$,

giving us our two roots $\displaystyle r_1=\phi=\frac{1+\sqrt{5}}{2}$ and $\displaystyle r_2=1-\phi=\frac{1-\sqrt{5}}{2}$. The equation becomes

$F_n=c_1\phi^n+c_2(1-\phi)^n$,

in which we still have to find $c_1$ and $c_2$. For this, we must use the initial conditions of the recurrence. Knowing

$F_0=0$

and

$F_1=1$

(which is still the normal Fibonacci recurrence but starting at $n=0$ rather than $n=1$), we find two equations in two unknown:

$F_0=c_1\phi^0+c_2(1-\phi)^0=0$

$F_1=c_1\phi^1+c_2(1-\phi)^1=1$

Solving the system we find $\displaystyle c_1=\frac{1}{\sqrt{5}}$ and $\displaystyle c_2=-\frac{1}{\sqrt{5}}$. Plugging back $c_1$ and $c_2$ in

$F_n=c_1\phi^n+c_2(1-\phi)^n$,

we get

$F_n=\frac{1}{\sqrt{5}}\phi^n-\frac{1}{\sqrt{5}}(1-\phi)^n$,

or

$\displaystyle F_n=\frac{\phi^n-(1-\phi)^n}{\sqrt{5}}$.

…and we’re done.