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.

39.953605
-75.213937

### Like this:

Like Loading...

*Related*

##
About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

Color me impressed. Previous posts on the golden ratio seemed more about curiosity than application. This is a formula I may just use.

This also leads to the result, which I’ve always remembered from my old college abstract algebra class, that the ratio of terms of the Fibonacci sequence approaches phi. Set up the ratio and take the limit, though one could also say that as the corrective term shrinks, the elements of the sequence approach (phi^n)/sqrt(5), and the sequence approaches a geometric one… One could take that further and use the general formula for the sum of a geometric series to at least approximate the sums you began all this with, but it’d take a fairly large n to get good results…

Just found your blog today, and I’m really enjoying it!

Kevin,

Indeed it does! There’s all kinds of fun stuff there that I haven’t mentioned.

Glad you’re enjoying it!

Thank you very much for these clear explanations of phi properties. I tried to solve some exercices about it and I was a bit lost…

I’m in “premiere” in a French high school and I have to do for the next week a big, big work in a group about a subject with both Maths and Biology (OK, we have to do it for months, but we’re a bit late…).

We chose the golden number and how you can find it in nature, but we didn’t find some demonstrations… (that’s right, we’re not cleverer than a banana). I’ve been looking for these on the web for long and you’re the first site which I understand !

Thank you !