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
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.

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search