Proof of Convergence

Date: 09/29/2000 at 08:42:45
From: Marc Decroos
Subject: Golden Section and Fibonacci

The Dr. Math FAQ illustrates how the Fibonacci rectangles are converge 
toward the Golden Section. 

  Golden Ratio, Fibonacci Sequence
  http://mathforum.org/dr.math/faq/faq.golden.ratio.html   

But that page does not prove that this is so.

They could be converging to another "nice" number. Why the magic 
1.618033989...?

Kind regards,
Marc

Date: 09/29/2000 at 13:43:22
From: Doctor Rob
Subject: Re: Golden Section and Fibonacci

Thanks for writing to Ask Dr. Math, Marc.

You can prove that F(n+1)/F(n) converges to (1+sqrt[5])/2 by first 
proving the Binet Formula for F(n). Let

     a = (1+sqrt[5])/2
     b = (1-sqrt[5])/2

Notice that

         1 < a
        -1 < b < 0
     a + b = 1
     a - b = sqrt(5)
       a*b = -1
       a/b = -a^2
     a - b = sqrt(5)

Now a and b are roots of the quadratic equation

     0 = (x-a)*(x-b)
     0 = x^2 - (a+b)*x + (a*b)
     0 = x^2 - x - 1

That means that

     a^2 = a + 1
     b^2 = b + 1

Now using this, you can prove the Binet Formula

     F(n) = (a^n-b^n)/(a-b)

by using the Principle of Mathematical Induction along with the above 
facts about a and b, and the definition of the Fibonacci numbers,

     F(0)   = 0
     F(1)   = 1
     F(n+1) = F(n) + F(n-1)

Once you have proved the Binet Formula, you can see that

     F(n+1)/F(n) = (a^[n+1]-b^[n+1])/(a^n-b^n)
                 = (a*a^n-a*b^n+a*b^n-b*b^n)/(a^n-b^n)
                 = (a*[a^n-b^n]+b^n*[a-b])/(a^n-b^n)
                 = a + b^n*(a-b)/(a^n-b^n)
                 = a + (a-b)/([a/b]^n-1)

Now as n grows, |(a/b)^n| = a^(2*n) grows without bound (because 
a > 1), so the fraction in the last equation approaches 0. That proves 
that F(n+1)/F(n) approaches a, as claimed.

Another approach is to start with the recursion

     F(n+1) = F(n) + F(n-1)

and divide through by F(n):

     F(n+1)/F(n) = 1 + F(n-1)/F(n)
                 = 1 + 1/[F(n)/F(n-1)]

Now suppose that F(n+1)/F(n) approaches a limit L. Then F(n)/F(n-1) 
approaches that same limit L. By taking the limit as n increases 
without bound of the above equation, you find that

               L = 1 + 1/L
             L^2 = L + 1
     L^2 - L - 1 = 0

and L is one of the roots of the equations x^2 - x - 1 = 0, that is, 
L = a or b. Clearly L is positive, and b is not, so L = a. This proves 
that if F(n+1)/F(n) approaches a limit, that that limit must be a. 
There remains to show that the quotient does have a limit. That can be 
done by showing that

     |F(n+1)/F(n) - a| <= c*|F(n)/F(n-1) - a|

for some constant c with 0 < c < 1.  I leave it to you to figure out 
the value of the constant c and the proof of the above statement. Then

     |F(n+1)/F(n) - a| <= c^(n-1)*(a-1)

and the latter approaches 0 as n grows without bound.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/