## 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. Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in famous numbers, fibonacci, golden ratio, proof. Bookmark the permalink.

### 4 Responses to Explicit Fibonacci numbers

1. Steve Gilberg says:

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

2. Kevin says:

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!

3. Brent says:

Kevin,

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

4. Léa says: