The non-recursive formula for Fibonacci numbers
Discover more from The Palindrome
The non-recursive formula for Fibonacci numbers
(via the magic of power series and generating functions)
The Fibonacci numbers form one of the most famous integer sequences, known for their intimate connection to the golden ratio, sunflower spirals, mating habits of rabbits, and several other things.
By definition, the Fibonacci numbers are defined by a simple second-order recursion.
This is usually also the example illustrating that recursive functions are not always a good idea in computing.
For instance, consider the following function. (It is written in Python, but it is easy to translate to other programming languages.)
Even for small n-s, fibonacci(n) takes a long-long time to run.
The first improvement is usually introducing memoization, which significantly cuts the runtime. Or perhaps to introduce a matrix formula, packaging the recursion into matrix multiplication.
What’s usually not known is that the Fibonacci numbers have a simple and beautiful closed-form expression, written in terms of the golden ratio.
This is called the Binet formula. In this post, we are going to derive it from the first principles.
Why should you be interested in this? Besides the practical use, the way towards Binet’s formula teaches us an extremely important technique: power series and generating functions.
Power series are a stunningly powerful tool, used throughout mathematics and computer science. Let’s see what are they!
Power series
By definition, a power series is the infinite sum of monomials. You can think about them as “polynomials of infinite degree”. The coefficients of the monomials are called the coefficients of the power series.
If the power series sums to the function a(x), we say that it is the power series of a(x).
One of the most important examples is the famous geometric series. We’ll use this to derive the closed formula for the Fibonacci numbers.
A power series is fully determined by its coefficients: two power series are equal if and only if their coefficients are equal. This is called the uniqueness property of power series.
Power series are also linear in a sense. That is, summing two power series is the same as summing their coefficients.
The uniqueness and linearity are extremely useful in the widest range of circumstances. For instance, we can use them to find a closed-form expression for the Fibonacci numbers!
Let’s see how.
The generating function of the Fibonacci numbers
What happens if we define a power series via the Fibonacci numbers? Let’s find out. This is called the Fibonacci generating function.
Here is our two-step plan: we’ll use the recursion to obtain a closed-form expression for F(x), then figure out its coefficients by reducing it to the geometric series.
First, about that recursion. Do you recall how the Fibonacci numbers were initially defined? We can multiply each term with the corresponding monomial to obtain the terms of the generating function on both sides.
After summing the terms, we obtain an equation - for the generating function!
With a tiny bit of algebra, we can find the closed form of F(x)! Here it is below.
The right-hand side is a rational fraction, that is, the fraction of two polynomials.
How are we going to find the power series for this particular rational fraction? By taking a closer look at the polynomial 1 - x - x² in the denominator.
The golden ratio and the generating function
The second-degree polynomial 1 - x - x² is a famous one. Why? Let’s take a look at its roots via the quadratic formula.
This is the golden ratio and its conjugate!
These two numbers are quite special. Geometrically speaking, they describe the segments a and b such that the ratio of a to b is the same as a to a + b.
Besides its geometric properties, the golden ratio and its conjugate are also special in an algebraic way. Their sum and product are 1 and -1 respectively, while their difference is √5.
Take note of these, as they’ll come in shortly.
What can we do with all of these? As the golden ratio and its conjugate are the roots of 1 - x - x², we can decompose this quadratic polynomial into the product of two linear terms.
Enter the partial fraction decomposition.
Partial fraction decomposition of the generating function
We love rational fractions for one main reason: because they can be decomposed into the sum of geometric series.
In the case of the Fibonacci generating function, the decomposition is particularly simple.
We can find a and b by adding the two fractions together.
Using the fact that two polynomials are equal if and only if their coefficients are equal leads to a simple system of linear equations.
This can be easily solved in terms of the golden ratio and its conjugate.
Applying this to the Fibonacci generating function, we can obtain its final form. (Recall that addition and scalar multiplication of power series can be done coefficientwise.)
And thus, we finally obtain the Binet formula! (As follows from the uniqueness property of power series.)
If you think about it for a second, this is quite a remarkable formula. Both the golden ratio and its conjugate are both irrational numbers, yet the result is an integer.
Conclusion
The Fibonacci numbers are one of the most famous and well-studied integer sequences of all time. They appear in many places, for instance, introductory programming courses use them to demonstrate why recursive functions can be a bad idea.
Because of this, the Fibonacci numbers are can teach us lots of new tricks. In this post, we used them to demonstrate the strength of power series and generating functions: a few simple principles and a bit of algebra yield a closed formula for a recursively defined sequence.
Of course, the so-called Binet formula is useful and beautiful on its own, but the main lesson is in the application of power series. When calculus, algebra, and combinatorics intersect, powerful tools can emerge.