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 these ads
This entry was posted in famous numbers, fibonacci, golden ratio, proof. Bookmark the permalink.

4 Responses to Explicit Fibonacci numbers

  1. 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.

    Glad you’re enjoying it!

  4. Léa says:

    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.