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

  2. MDV


    Jul 26, 2021
    Likes Received:
    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.
    paulejking, Jul 26, 2021
    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.