(I'm not a 'mathematician; but just a coder with a casual fascination of numbers, so excuse me if my notation is not
good! )
I recently came across Binet's formula for calculating Fibonacci numbers, and it seemed nice to have an analytic formula.
http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html
It occurred to me that if I do a binomial expansion of (1 + a )^n and of (1 - a)^n , (where a = root(5) ) then the even power terms of both series are the same since a^p == (-a)^p for even p.
SO... subtracting the two series to get the numerator in Binet's formula, we get a series of ODD powers of a,...
2(n,1)a + 2(n,3)a^3 + 2(n,5)a^5 +..... where (n, m) = Binomial coefficient (n,m)
Now Multiplying both denominator and numerator in Binets formula by root(5) ie. 'a', the root 5 term disappears and we cancel the '2' by reducing the power of 2 in the denominator, to get:
Fibonacci(n) = ( (n,1)5 + (n,3)5^2 + (n,5)5^4 + …. ) / 2^(n-1)
This means we have got rid of the transcendental root 5,
It seems an obvious reduction BUT it still means calculating the terms in the series. I've coded it to test, and it works,
( In my code test I can calculate the binomial coefficients iteratively (no need for factorials) and several other optimisations BUT it is still a series of (n/2) terms. )
It would be nice if there was someway of 'collapsing' the series back to functions, as I would then have a nice analytic formula for Fibonnaci using only integers.
I cant seem to find anything on this with Google.... maybe somebody with better maths than me has any ideas on how to improve this ????
Interestingly it appears that the numerator is a multiple of 2^(n-1) before dividing it (shift right by n-1) in my code. So for fun I'm now trying to use this observation and other stuff to optimize the code.... but of course it's still a loop.....
Thanks!!!!!!
good! )
I recently came across Binet's formula for calculating Fibonacci numbers, and it seemed nice to have an analytic formula.
http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html
It occurred to me that if I do a binomial expansion of (1 + a )^n and of (1 - a)^n , (where a = root(5) ) then the even power terms of both series are the same since a^p == (-a)^p for even p.
SO... subtracting the two series to get the numerator in Binet's formula, we get a series of ODD powers of a,...
2(n,1)a + 2(n,3)a^3 + 2(n,5)a^5 +..... where (n, m) = Binomial coefficient (n,m)
Now Multiplying both denominator and numerator in Binets formula by root(5) ie. 'a', the root 5 term disappears and we cancel the '2' by reducing the power of 2 in the denominator, to get:
Fibonacci(n) = ( (n,1)5 + (n,3)5^2 + (n,5)5^4 + …. ) / 2^(n-1)
This means we have got rid of the transcendental root 5,
It seems an obvious reduction BUT it still means calculating the terms in the series. I've coded it to test, and it works,
( In my code test I can calculate the binomial coefficients iteratively (no need for factorials) and several other optimisations BUT it is still a series of (n/2) terms. )
It would be nice if there was someway of 'collapsing' the series back to functions, as I would then have a nice analytic formula for Fibonnaci using only integers.
I cant seem to find anything on this with Google.... maybe somebody with better maths than me has any ideas on how to improve this ????
Interestingly it appears that the numerator is a multiple of 2^(n-1) before dividing it (shift right by n-1) in my code. So for fun I'm now trying to use this observation and other stuff to optimize the code.... but of course it's still a loop.....
Thanks!!!!!!
