Bill Amend’s popular strip *Foxtrot* nearly always makes me smile, but last Sunday’s strip made me laugh all day. The wildly (and undeservedly) popular bestseller *The Da Vinci Code* introduced Fibonacci numbers to the general public. The series consists of whole numbers such that each number is the sum of the previous two. The series starts out like this:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

Despite the simplicity of the series, there is no known method for generating the *n*th term in the series without generating all the intervening terms. Stranger still, the ratio between two adjacent Fibonacci numbers approaches the golden ratio as the numbers increase. The golden ratio is the ratio between two numbers *a* and *b* such that *a*/*b* = *b*/(*a + b*). A little algebra serves to show that this ratio is about:

0.618 033 988 749 894 848 204 586 834 366

Another curiosity about this number: it’s inverse is the same as adding 1 to it. Again, it’s not hard to show that if *n* = *a*/*b*, then 1/*n* = *n* + 1.

There’s more.

Consider any rectangle. It can be thought of as figure constructed by adding squares of different sizes together. For example, a 3 × 5 rectangle can be thought of as consisting of a 3 × 3 square, a 2 × 2 square, and two 1 × 1 squares, like this:

Now imagine a rectangle where the ratio of the length to the width is the golden ratio. If you divide it into the largest square and a left over rectangle, the remaining rectangle is still a golden rectangle. If you divide that rectangle into a largest square and a rectangle, the remaining rectangle is still a golden rectangle. So the process of dividing the rectangle into squares continues *ad infinitum* and at every step there is always a golden rectangle still left to be divided. It’s not hard to see why. We know that the golden ratio is given by *a*/*b* = *b*/(*a* + *b*). Suppose the rectangle has width *b* and length *a* + *b*. Then the largest square to be taken from the rectangle is *b* × *b*, leaving a rectangle with width *a* and length *b*. But the ratio of *a* to *b* is the golden ratio, hence another golden rectangle.

Since the golden ratio approximates the ration between two adjacent Fibonacci numbers, we can use it to determine the next Fibonacci number in a sequence. For example, the series above ended at 377. The next number should be about 377/0.618033… ≈ 609.999. So the next number should be 610, and we can confirm that it is by adding 233 + 377 = 610.

Thanks. Do you by any chance have a proof?

“there is no known method for generating the nth term in the series without generating all the intervening terms”

Actually, there is a very simple closed formula for generating the sequence, and it too involves the Golden Ratio. If we let p = (1 + sqrt(5))/ 2 = the golden ratio, then the nth Fibonacci number F(n) can be found as follows:

F(n) = (p^n – (-p)^-n)/sqrt(5)

No need to generate F(1) through F(99) to generate F(100).

I too loved the Fibonachos strip.