Fibonacci SequencesDate: 01/08/98 at 08:30:38 From: Anonymous Subject: Fibonacci Sequences In a Fibonacci sequence, where the recursive formula is: a sub n = a sub n-1 + a sub n-2 where a1 = 1 and a2 = 1 The Explicit Formula would be: An = ((((1 + ?5) / 2)^n - ((1 - ?5) / 2)^n) / ?5) So help me prove the following: ((((1 + ?5) / 2)^n - ((1 - ?5) / 2)^n) / ?5) = ((((1 + ?5) / 2)^n-1 - ((1 - ?5) / 2)^n-1) / ?5) + ((((1 + ?5) / 2)^n-2 - ((1 - ?5) / 2)^n-2) / ?5) ?5 is the square root of 5 Thank you. Date: 01/15/98 at 14:13:12 From: Doctor Joe Subject: Re: Fibonacci Sequences Hi, I'll get you started on proving that ((((1 + ?5) / 2)^n-1 - ((1 - ?5) / 2)^n-1) / ?5) + ((((1 + ?5) / 2)^n-2 - ((1 - ?5) / 2)^n-2) / ?5) equals ((((1 + ?5) / 2)^n - ((1 - ?5) / 2)^n) / ?5) (keeping in mind that ?5 = the square root of 5). The first thing that strikes me about this problem is that it is hard to see what we're trying to prove with all of these terms running around. In these situations, it is best to look for a substitution that clarifies what you are dealing with. One useful substutition defines x and y such that x = (1 + ?5)/2 and y = (1 - ?5)/2 Substituting these values into our equation, we get: (1/?5)*(x^(n-1) - y^(n-1) + x^(n-2) - y^(n-2)) = (1/?5)*(x^n - y^n) as the equation we are trying to prove (let's call this equation 1). Remember that when proving an equation to be true, you have to show that the terms on both sides of the equals sign match exactly. To solve this problem, let's try to make the more complicated side of equation 1 (the left side) look exactly like the less complicated side (the right side). Let's look at the lefthand side. Note that (1/?5)*(x^(n-1) - y^(n-1) + x^(n-2) - y^(n-2)) = (1/?5)*(x^(n-1) + x^(n-2) - y^(n-1) - y^(n-2)) = (1/?5)*(x^(n-2) * (x+1) - y^(n-2) * (y+1)) (factoring an (x+1) out of the terms with an x in them and factoring a (y+1) out of the terms with a y in them). Now in order to make this look like the righthand side of equation 1, we need to reduce x^(n-2)*(x+1)-y^(n-2)*(y+1) to (x^n - y^n). First focus on the exponents on x and y. Right now, both x and y have an exponent of n-2. Factor an x^n out of x^(n-2) and factor a y^n out of the y^(n-2). Now you will have the correct exponents on x and y. But the factoring you did produced some other terms that have to be dealt with. In order for the lefthand side to look exactly like the righthand side, these troublesome terms will have to disappear. Make them disappear by substituting the explicit values for x and y into the troublesome terms, do a little algebra and voila! They will trouble you no more. I hope this helps you. Please write back if you need more help on this or other problems. If you would like to learn more about the "golden ratio" (which equals (1 + ?5)/2), please look at the FAQ labeled "golden ratio" at http://mathforum.org/dr.math/faq/ -Doctors Naomi and Joe, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/