Monday, December 8, 2008

Proof of the Fibonacci sequence and Golden Ratio

This is a proof of the Fibonacci sequence and its relation to the Golden Ratio.

If we consider the equation (x^2) - x - 1 we find it can be solved by letting x=a=(1+sqrt(5))/2)=1.618 which is the golden ratio.

We can prove that all numbers in the Fibonacci sequence produces solutions for this equation if we can prove that any number in the sequence f(n) is less than or equal to any solution before it a^(n-1)

We start by testing the first two cases which is a=1 and a=2, (1 and 2 are both Fibonacci numbers) thus we have 1 < = (a^0) = 1, and 1 < = a^1 = (1+sqrt(5))/2)

Now we prove the general case,

f(n) = f(n-1) + f(n-2) where f(n) is any Fibonacci number (in other words a Fibonacci number is generated by the addition of the two previous numbers, consider the first few numbers in the Fibonacci sequence: (1,2,3,5,8...)

f(n-1) + f(n-2) < = a^(n-2) + a^(n-3)

= a^(n-3) * (a+1) by factorization

= a^(n-3) * (a^2) (because a+1 is a solution to the equation (x^2) - x - 1

= a(n-1)

so therefore f(n) < = a^(n-1)