Don’t worry, this post isn’t going to be X-rated! By explicit I mean not recursive. Remember that the Fibonacci numbers are defined recursively, that is, each Fibonacci number is given in terms of previous ones: . Doesn’t it make you wonder whether there’s a formula we could use to calculate directly in terms of n, without having to calculate previous Fibonacci numbers?
It’s a great question. Such a formula would be called an explicit formula, and in general, you could devote a whole graduate-level class to the topic of turning recursive formulas into explicit ones! However, finding an explicit Fibonacci formula isn’t as difficult as all that. In fact, the key to understanding it is the “golden powers” identity from my last post:
First of all, we note that every single piece of the above identity’s proof works for just as well as for , so it is also true that
Now, consider subtracting one from the other:
But now it is a simple matter to solve for :
Amazing! It seems weird that a formula to generate integers involves all these strange non-integers like and , but there it is. We can even simplify this further by noting that since has an absolute value smaller than 1, in general is very small. So, what’s happening here is that is just a tiny bit bigger or smaller than , and subtracting off the (very small) gives exactly. We could just as well compute and round (up or down) to the nearest integer:
Excellent! Now we can compute Fibonacci numbers directly, without computing all the previous ones.