Binet's Formula

You’re probably familiar with the Fibonacci numbers. To generate the famous sequence, start with 0 and 1 and add the previous two terms together to get the next.

\(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...\)

The Fibonacci numbers are defined by a recurrence relation, which is just a fancy way to say that the next term depends on the previous terms. If you wanted to compute the 25th number in the sequence, you would have to sit there and compute one term after another until you got there.

If that sounds too tedious, there is a remarkable shortcut known as Binet’s Formula, named after the 19th century French mathematician Jacques Philippe Marie Binet. It is surprisingly…..messy:

\(\frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}} \left( \frac{1 - \sqrt{5}}{2}\right)^n\)

As an example, to compute the 25th Fibonacci number, replace n with 25 and punch the formula into a calculator.

\(\frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2}\right)^{25} - \frac{1}{\sqrt{5}} \left( \frac{1 - \sqrt{5}}{2}\right)^{25} = 75025\)

The remarkable thing about this formula is that it involves the square root of 5, an irrational number—the decimal representation goes on forever with no apparent pattern.

\(\sqrt{5} = 2.236...\)

I’d expect a formula that involves exponents and irrational numbers to spit out more irrational numbers, or at least messy numbers with many decimal places. Amazingly, that is not what happens when n is replaced by a whole number. Everything works out just right, and the answer always turns out to be a whole number (and a Fibonacci number).

Binet’s formula holds one other surprise—it is closely tied to the golden ratio, usually denoted by the Greek letter phi.

\(\phi = \frac{1 + \sqrt{5}}{2} = 1.618...\)

With a little rearrangement, the formula can be rewritten in terms of the golden ratio.

\(\frac{\phi^n - \left( \frac{-1}{\phi} \right)^n}{\sqrt{5}}\)

Who would have guessed that the Fibonacci sequence, a sequence of whole numbers, would be intricately tied to a formula involving irrational numbers—and not just any irrational number, but the famous golden ratio!