The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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   

But that page does not prove that this is so.

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

Kind regards,

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   
Associated Topics:
High School Basic Algebra
High School Fibonacci Sequence/Golden Ratio
High School Sequences, Series

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.