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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: