Formula for the Fibonacci Sequence

Date: 4/8/96 at 2:25:24
From: Anonymous
Subject: Implicit formula for the Fibonacci Sequence

What is the implicit formula for the Fibonacci sequence?
(Meaning, the non-recursive one).

Date: 5/28/96 at 20:26:37
From: Doctor Pete
Subject: Re: Implicit formula for the Fibonacci Sequence

Lucas' formula for the nth Fibonacci number F(n) is given by

         ((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n
  F(n) = ------------------------------------- .
                         sqrt(5)

Here is a proof.  Let p = (1+sqrt(5))/2, and q = (1-sqrt(5))/2.  Then 
p^2 = 
(1+sqrt(5))^2/4 = (3+sqrt(5))/2 = 1+(1+sqrt(5))/2 = 1+p.  
So p^3 = 
p(p+1) =
p^2+p = (p+1)+p = 2p+1, and we make a list:

   p   = (1)p+(0)
   p^2 = (1)p+(1)
   p^3 = (2)p+(1)
   p^4 = (3)p+(2)
   p^5 = (5)p+(3) ...

And you'll notice that we're getting Fibonacci numbers on the 
right hand side, so it looks like p^n = F(n)p+F(n-1).  

A proof by induction is easy; if this is true, then 
p^(n+1) = p(p^n) = 
F(n)p^2+F(n-1)p = 
F(n)(p+1)+F(n-1)p =
(F(n)+F(n-1))p+F(n) = 
F(n+1)p+F(n), since we know the recursive formula
F(n)+F(n-1)=F(n+1).  

Similarly, q^n = F(n)q+F(n-1).

With this in mind, think about the difference of these two 
relations:  

we have p^n-q^n = F(n)(p-q), so F(n) = (p^n-q^n)/(p-q).  
But p-q = (1+sqrt(5))/2-(1-sqrt(5))/2 = sqrt(5), so we get 
Lucas' formula.

-Doctor Pete,  The Math Forum