Fibonacci sequence

Date: 1/28/96 at 11:14:46
From: Kate Bauer and Eric Lindblom
Subject: Fibonacci sequence

What is the explicit formula for the Fibonacci numbers?   
 
Thank you very much for your help, 

Kate Bauer 

Date: 6/5/96 at 8:4:27
From: Doctor Charles
Subject: Re: Fibonacci sequence

There is an explicit formula for the Fibonacci numbers and it involves 
the Golden Mean (=phi=(1+sqrt(5))/2). However it is very ugly compared 
to the rest of the Fibonacci sequence's properties.

My definition of the sequence starts at 0 but you may prefer 1. 0 is 
easier to work with in this problem and it is easy to convert back at 
the end.

We have to solve:  f_0 = 1       f_1 = 1

            f_n = f_n-1 + f_n-2

To solve difference equations like this (the technique is analogous to 
linear 2nd order differential equations) we first solve the auxiliary 
equation:

          k^2 = k + 1

and get     k = (1+sqrt(5))/2  or  (1-sqrt(5))/2
              =  phi           or  (1 - phi)

This gives that any sequence of the form 

         f_n = a * (phi)^n + b * (1-phi)^n

will satisfy the difference equation: 

         f_n = f_n-1 + f_n-2. 

You can check this by substituting the formula into the difference 
equation.

Now we just have to find a and b such that f_0 = 1 and f_1 = 1.

         f_0 = 1 = a + b
         f_1 = 1 = a * phi + b * (1 - phi).

So we get  b (2*phi - 1) = phi - 1
   and     a (2*phi - 1) =    phi.

but 2*phi - 1 = sqrt 5
so we have 

   f_n = phi/sqrt(5) * (phi)^n  +  (phi-1)/sqrt5 * (1-phi)^n

       = phi^(n+1) / sqrt(5)    -  (1-phi)^(n+1) / sqrt(5)

and if you want your sequence to start at 0, not 1, you get the 
simpler:

   f_n = phi^n / sqrt(5)  -  (1-phi)^n / sqrt(5)

I hope this helps!

-Doctor Charles,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/