A Better Way to Calculate the Fibonacci Numbers

Published in

Technological Singularity

8 min readDec 28, 2023

https://unsplash.com/photos/a-close-up-of-a-shell-with-a-white-background-cNtMy74-mnI?utm_content=creditShareLink&utm_medium=referral&utm_source=unsplash

You might have heard of the fibonacci numbers (don’t worry if you’ve haven’t — we’ll explain them below) but did you know we there is a way of calculating them without having to use recursion called Bidet’s formula.

What are the Fibonacci numbers?

The Fibonacci numbers are the sequence of numbers:

We define these starting with 1,1 then every number afterwards is the sum of the previous two. So the third number is

And the fourth is

We can write this using the following formula:

Recursive code

When you’re first learning to program you may have written some code to calculate the find the nth fibonacci number.

def find_nth_fib(n):
    if n == 1:
        return 1
    if n == 2:
        return 1
    return find_nth_fib(n-1) + find_nth_fib(n-2)

The code above works by computing all the previous fibonacci numbers in order to find the one you’re looking for.

Is there another way?

However, there is a way of calculating the nth fibonacci number directly and it’s given by Bidet’s formula:

Proof of it

This formula looks really random so let’s walk through the proof of it to see where it comes from.

Define a series

To prove this formula we’ll start by defining the following series:

Where

is the ith fibonacci number.

Construct two other series

Now let’s construct two other related series:

and

Take difference

Now let’s note that

Now let’s write this a different way

We now remember that

so all but the first two terms go to zero leaving:

Next, we use the fact that

to get

So after all that we get

Finding roots

We can solve this quadratic equation using the quadrartic formula

This means we can factor our equation it into:

So we can write:

Partial Fractions

The next step is to use partial fractions to split out this nasty looking denominator into the the sum of two terms:

To find A and B we know that:

This most hold for all x, so we can specific x to make this calculation easy. We’ll pick

Putting this in we get:

This means that

We’ll do a similar thing again but this time use

So we get

Putting these values back in we get:

Geometric series

Now we have nice expression for F(x) but we wanted to be able to work out the coeffecients of each term rather than just the value of the series. Luckily, we can do some clever rewriting.

There is a famous series called the Geometric Series given by:

We can use this to rewrite our expression from the previous section. Starting with

We can rewrite it as:

This means it is now in the right form to apply the geometric series so we get:

We can now do the same thing for:

Which gives us:

Factor

Finally, we can take these two new expressions we found and put them back in. So

becomes

Next, we’ll get the x on it’s own

Finally, we’ll combine the two sums to get:

Getting the Fibonacci numbers back out

We know have a complicated looking expression but what does it have to do with the fibonacci numbers. We’ll remember that:

So comparing it to

We see that

which completes our proof

Bonus: proof that F converges

We’ve completed the main body of our proof but for some of our steps we treated F(x) just like a number. But it is really an infinite sum

Most of these infinite sums just get infinitely big or infinitely small (we say these sums are divergent). So when working with them, we have to be careful as some steps are not justified.

Thankfully, the sum we have defined above actually becomes a number (we say it converges to a number) so long as

so we can work with it nicely.

To finish off our proof we will check that F(x) converges

To prove our series F(x) is convergent. We’ll use a common technique: show that the terms of our series are smaller than the terms of some other series. Then showing that the other series converges. To do this we’ll need two convergence tests