Because Linear Recurrences are Sexy
As you probably already know, the Fibonacci sequence is defined as follows:
This is a recursive definition, meaning (in this case, at least) that in order to find the value of F(n), you must first find the values of F(n-1) and F(n-2), each of which requires another step of recursion, which requires another step and so on.
As you might imagine, this calculation is quite cumbersome. After a bit of working out, you might ask yourself: “is there a better way?” or perhaps more specifically, “is there a direct formula I can use to find the nth Fibonacci number?”
To my mind, there are two ways to answer this question:
Google “explicit formula for the Fibonacci sequence,” click the first link, and be on your merry way.
Invest a bit of time to actually understanding the problem, and its eventual solution
Here is option 2:
The first thing I want to introduce is the idea of a Generalized Fibonacci sequence. Basically, a Generalized Fibonacci sequence is a sequence that follows the same recursion as before, but starts with different numbers. I’ll list some examples:
Collectively, all these sequences are an example of something called a “vector space.” That means two things:
1. Adding together two Fibonacci sequences (component-wise) results in another Fibonacci sequence.
2. Multiplying a Fibonacci sequence by a regular number results in another Fibonacci sequence:
You can think about these operations geometrically by imaging a sequence starting with (a, b, ….) as the 2d vector (a,b) on the normal coordinate grid.
We can then perform the same calculations as before, but using the more-familiar version of vector addition:
The important revelation here is that, through multiplication and addition, we can combine two Fibonacci sequences to create another Fibonacci sequence. Remember that.
Back to the original problem. We’re trying to find an explicit formula for the nth Fibonacci number. We don’t know how to do that yet, but it might be helpful to think of different sequences that do have an explicit formula.
If you’ve read some of my previous blogs, you’ll already know of one:
The nth term of this sequence is a nice, easy xn-1.
Close observers will notice that this isn’t just one sequence. x2 = x+1 is quadratic, and thus has two solutions. Let’s give these two sequences names:
Because these sequences both have explicit forms, we can combine them through addition and multiplication to create other sequences with explicit forms
The nth term of this sequence is given by 2αn-1 + βn-1.
Our objective is to find a similar formula for the nth Fibonacci number. Just as in the previous example, we’re going to add multiples of the A and B sequences together, meaning our end result will look like this:
With the explicit form.
All we have to do is find the correct values for c and d.
Because the 1st Fibonacci number is 1, we can substitute n=1, and set the above expression equal to 1.
Similarly, we substitute n=2 and set the expression equal to 1 (because the 2nd Fibonacci number is 1)
Now that we have two equations, and two unknowns, we should be able to find the proper values for c and d.
In an effort not to bore you, I’ll be going with the “just google it” approach:
Let us all take a moment to glorify the one true Wolfram Alpha.
Simplifying those answers, we get c = 0.7236… and d = 0.2764…
Plugging this back into our equation, we claim that the nth Fibonacci number is given by
But does it work?
I’d say so.