Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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

    
Associated Topics:
High School Fibonacci Sequence/Golden Ratio

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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/