Proof of ConvergenceDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/