A Better Way to Calculate the Fibonacci Numbers
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
Ratio Test
For a series:
The ratio test looks at the ratio between adjacent terms:
And then takes the limit as we go to infinity
This tells us if the terms eventually stay close to each and the series converges or not. Formally it says:
then the series converges. If
then the test doesn’t tell you one way or the other. And if
then the series is divergent
Comparison Test
Another useful way to work out if a series converges is the comparison test
If we have the series of positive numbers
and a convergent series of positive numbers
and after some point in the series:
then
also converges
2^n series
Now we can prove that F(x) converges
Consider the series
We can show that
by applying induction.
For the case n=1 we have
Now we assume it for n=k, so we have
Next, we consider n=k+1,
Which by our assumption:
So now we need to show that
is convergent.
To do this we apply the ratio test:
Now
only if x< 1/2
Therefore our series F(x) converges if x < 1/2