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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum