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

Discussion in 'Number Theory' started by MDV, Jan 18, 2020.

  1. MDV


    Jan 18, 2020
    Likes Received:
    (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.

    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.....

    MDV, Jan 18, 2020
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.