Explicit Fibonacci numbers

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: $F_n = F_{n-1} + F_{n-2}$ . Doesn’t it make you wonder whether there’s a formula we could use to calculate $F_n$ 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:

$\varphi^n = F_n \varphi + F_{n-1}.$

First of all, we note that every single piece of the above identity’s proof works for $\hat{\varphi}$ just as well as for $\varphi$ , so it is also true that

$\hat{\varphi}^n = F_n \hat{\varphi} + F_{n-1}.$

Now, consider subtracting one from the other:

$\begin{array}{rcl} \varphi^n - \hat{\varphi}^n &= & F_n \varphi + F_{n-1} - (F_n \hat{\varphi} + F_{n-1}) \\ &= & F_n (\varphi - \hat{\varphi}) = F_n \sqrt{5}. \end{array}$

But now it is a simple matter to solve for $F_n$ :

$\displaystyle F_n = \frac{\varphi^n - \hat{\varphi}^n}{\sqrt{5}}.$

Amazing! It seems weird that a formula to generate integers involves all these strange non-integers like $\varphi$ and $\sqrt{5}$ , but there it is. We can even simplify this further by noting that since $\hat{\varphi} \approx -0.618\dots$ has an absolute value smaller than 1, in general $\hat{\varphi}^n/\sqrt{5}$ is very small. So, what’s happening here is that $\varphi^n/\sqrt{5}$ is just a tiny bit bigger or smaller than $F_n$ , and subtracting off the (very small) $\hat{\varphi}^n/\sqrt{5}$ gives $F_n$ exactly. We could just as well compute $\varphi^n/\sqrt{5}$ and round (up or down) to the nearest integer:

$\displaystyle F_n = \left[ \frac{\varphi^n}{\sqrt{5}} \right].$

Excellent! Now we can compute Fibonacci numbers directly, without computing all the previous ones.

About Brent

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

View all posts by Brent →

4 Responses to Explicit Fibonacci numbers

Steve Gilberg says:

September 14, 2007 at 10:21 am

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

May 30, 2008 at 11:34 am

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!
Brent says:

May 30, 2008 at 12:19 pm

Kevin,

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

Glad you’re enjoying it!
Léa says:

February 16, 2010 at 6:46 am

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 !

Comments are closed.