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}},



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


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


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

First, we must make the recurrence take the form


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


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:


has roots given by


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


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




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



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


we get



\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: Logo

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: