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
Math Forum Home || Math Library || Quick Reference || Math Forum Search