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:
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 , , and .
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
has roots given by
Using this with , , we find
giving us our two roots and . The equation becomes
in which we still have to find and . For this, we must use the initial conditions of the recurrence. Knowing
(which is still the normal Fibonacci recurrence but starting at rather than ), we find two equations in two unknown:
Solving the system we find and . Plugging back and in
…and we’re done.