how about some proof?

So it looks like the ratio between two consecutive terms in the Fibonacci sequence gets closer and closer to the Golden Ratio as you go farther in the sequence. But "looks like" isn't good enough. We need to prove:

Johannes Kepler's Proof:^[6] We rely on Binet's formula, which is a closed-form expression for the n^th Fibonacci number, expressed F(n):^[5]

But wait!--this looks nothing like the recursive Fibonacci function we defined earlier. Before we can use this formula in Kepler's proof, we're going to have to prove that it's true.

proof of Binet's formula^[7]

Word on the street is that Binet wasn't the first to come up with this formula, but who cares? To the winner goes the spoils. That's what I say.

Recall the recursive Fibonacci function F(n) for natural n:

F(n) =

1  F(n-1) + F(n-2)

if n <= 2  if n > 2

We will prove that Binet's formula,

, is equivalent.

First, we simplify this a bit. Let

, and

. Then

(use a calculator if you don't believe me that a-b = the square root of 5)

Also notice that a and b are roots of the quadratic equation

.

We are going to prove that Binet's formula is equivalent to the Fibonacci function by using the principle of mathematical induction. Basically, if we show that the formula holds for n=1, and that assuming the formula holds for n=k allows us to imply that it holds for n=k+1, we then can assume that the formula holds for all natural n.

First, we show that the formula holds for n=1. When n=1, Binet's formula gives us (a-b)/(a-b) = 1 = F(1). Terrific.

Now, for any k >= 1, we assume the formula holds for all n <= k. Specifically:

Add these equations together. The left-hand side becomes F(k+1) due to the recursive nature of the Fibonacci function. The right-hand side can be rearranged in a special way:

Because a and b are roots of , and . Replacing (a+1) and (b+1) with a² and b² in the expression above gives us Binet's formula for n = k+1:

That's it--we've satisfied both hypotheses of the Principle of Mathematical Induction, and so Binet's formula is true for all natural n. Now we can use it in Kepler's proof.

back to Kepler's proof

So, again, in order to prove:

we rely on Binet's formula, which we just proved:

Again, we can simplify this a bit. Let

, and

. Then

Now we perform some algebraic trickery. See if you follow:

		(« equation X)

Because of how we defined a and b we have:

So as n approaches infinity, and because a>1, the fraction in equation X approaches 0, leaving only a. And a is our Golden Ratio. So we're done.

trippy.

the ratio of consecutive Fibonacci numbers approaches the Golden ratio.