Fibonacci Sequences

Date: 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/