Friday, April 11, 2008

Fibonacci Numbers

You know the sequence:
1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Where each number is the sum of the 2 previous ones and the first 2 numbers are 1's.
So, I was curious if there is a formula for finding the nth Fibonacci number...
Here is what I found.

There is 1 rule that will guide you through the process (contact me if you want the prove)

if F(n) = a * F(n-1) + b * F(n-2)

and that c and d are 2 solutions to the quadratic equation x^2 = ax + b
then for any integer n, F(n) = r * c^n + s * d^n where r,s are real numbers

Applied to this case
(1 + √5)/2 and (1 - √5)/2 are solutions for x^2 = x + 1
so we have

F(n) = r * ((1 + √5)/2)^ n + s * ((1 + √5)/2)^n

since f(1) = f(2) = 1

r * (1 + √5)/2 + s * (1 -√5) / 2 = r * (3 + √5)/2 + s * (3 - √5)/2 = 1
r + s = 0 //subtract f(1) from f(2)
s = -r

r * (1 + √5)/2 - r * (1 - √5) / 2 = 1
r * (1 + √5 - 1 + √5)/2 = 1
r * √5 = 1
r = 1 / √5

Thus, the formula is:
F(n) = (1/√5)((1+√5)/2)^n - (1/√5)((1-√5)/2)^n

or to simplify things...

F(n) = (1/√5)(φ^n) - (1/√5)((1-φ)^n)
Where φ = Golden Ratio = (1+√5)/2

No comments:

Post a Comment