Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Fibonacci Sequence/Golden Ratio
High School Number Theory

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