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
Friday, April 11, 2008
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment