The Palindrome

Share this post

The non-recursive formula for Fibonacci numbers

thepalindrome.org

Discover more from The Palindrome

Mathematics for engineers, scientists, and other curious minds. Explaining things like your teachers should have, but probably never did.
Over 12,000 subscribers
Continue reading
Sign in

The non-recursive formula for Fibonacci numbers

(via the magic of power series and generating functions)

Tivadar Danka
Feb 7, 2023
19
Share this post

The non-recursive formula for Fibonacci numbers

thepalindrome.org
Share

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.

The Fibonacci sequence
The Fibonacci sequence

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

Fibonacci numbers in Python
Fibonacci numbers in Python

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.

The matrix form of the Fibonacci sequence
The matrix form of the Fibonacci sequence

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.

The closed form of Fibonacci numbers
The closed form of Fibonacci numbers

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!

The Palindrome is a reader-supported publication. To receive new posts and support my work, consider becoming a free or paid subscriber.

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

The power series of a(x)
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.

The geometric series
The geometric series

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.

The uniqueness of power series
The uniqueness 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 linearity of power series
The linearity of power series

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.

The recursive definition of the Fibonacci sequence
The recursive definition of the Fibonacci sequence

After summing the terms, we obtain an equation - for the generating function!

The generating function
The generating function

With a tiny bit of algebra, we can find the closed form of F(x)! Here it is below.

The closed form of the generating function for the Fibonacci sequence
The closed form of the generating function for the Fibonacci sequence

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.

The roots of 1 - x - x²
The roots of 1 - x - x²

This is the golden ratio and its conjugate!

The golden ratio and its conjugate
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.

The golden ratio in geometry
The golden ratio in geometry

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.

The algebraic properties of the golden ratio and its conjugate
The algebraic properties of the golden ratio and its conjugate

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.

Decomposition of 1 - x - x²
Decomposition of 1 - x - x²

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.

Partial fraction decomposition of the Fibonacci generating function
Partial fraction decomposition of the Fibonacci generating function

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

Partial fraction decomposition of the Fibonacci generating function
Partial fraction decomposition of the Fibonacci generating function

And thus, we finally obtain the Binet formula! (As follows from the uniqueness property of power series.)

The Fibonacci generating function and Binet's formula
The Fibonacci generating function and Binet's formula

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.

The Palindrome is a reader-supported publication. To receive new posts and support my work, consider becoming a free or paid subscriber.

19
Share this post

The non-recursive formula for Fibonacci numbers

thepalindrome.org
Share
Previous
Next
Comments
Top
New
Community

No posts

Ready for more?

© 2023 Tivadar Danka
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing