Binets formula (Fibonacci numbers) - eliminating root(5)

(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!!!!!!

 

Yes, but you never know what n is, and you would have to expand and "re-write" the formula each time for each n. The beauty of the existing formula is that the root-5's divide out or subtract out leaving a whole number. According to what you are saying, the number of terms left after cancellation appear to depend on n (I never tried it), so you don't know how many of them are there and what the coefficients are. Also, whether the final term in (1 - a)^n is positive or negative depends on n . That might be important.