Sometimes sequences of numbers are defined recursively, so that given the previous terms of the sequence we can find the next term. A classic example of this is the sequence of Fibonacci numbers, where every two consecutive terms determine the next term, and so if we are given the first two terms, we can calculate the whole sequence. However, if we wanted to, say, calculated the 1000th Fibonacci number, we’d have to start out with the first two, add them to compute the 3rd, add the second and third to compute the 4th, and so on, to slowly build up every single Fibonacci number before the 1000th in order to get there. It’d be much nicer if we had a formula for the Fibonacci sequence. That way, if we wanted the 1000th Fibonacci number, all we’d have to do is plug 1000 into the formula to compute it. Of course, the formula is only useful if it takes less time to crunch it out than it does to do it the brute-force way. A method of finding closed formulas for sequences defined by recurrences is the use of generating functions. Generating functions are functions which “encapsulate” all the information about a sequence, except you can define it without knowing the actual terms of the sequence. The power of generating functions comes from the fact that you can do things like add and multiply them together to create generating functions of other sequences, or write them in terms of themselves to find an explicit formula. Once you have an explicit form for a generating function, you can use some algebra to “extract” the information from the function, which usually means you can find a formula for the sequence in question.
Probably the most famous sequence defined by a linear recurrence is the Fibonacci sequence of numbers , defined by
that is, each term is the sum of the two previous terms. The first few terms are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 81. These numbers arise in nature. For example, consider modeling the population of some sort of asexually reproducing single-celled organism. Let’s suppose this species takes 1 day to reach “maturity,” after which it begins to asexually reproduce, and it takes 1 day to actually divide. Then, if the population on day is , then , since on the previous day there are cells but only of them are mature enough to start reproducing. For example, on day 1 there is 1 baby cell. On day 2, the baby cell becomes an adult. On day 3, the 1 adult has given birth, so there are 2 cells, 1 adult and 1 baby. On day 4, the baby has just matured and the adult has given birth again, yielding 3 cells, 2 adults and 1 baby. On day 5, the new baby matures and the 2 adults give birth, yielding 3 adults and 2 babies, and so on.
Now, it would be nice to be able to find a closed formula for , so that if we wanted to find , we don’t have to start from and build our way up. For example, if we had a sequence defined by and , then the numbers would be 1, 2, 4, 8, 16, etc. and it would be easy to see that a closed formula for this sequence is .
Intuitively, things whose growth rate is related to their current size grow exponentially. For example, the growth rate for our is , that is, the amount increases by each time is equal to how many there are right now. This is a model of cells dividing which do not require time to mature. The rate of growth for Fibonacci numbers is , so the growth rate is equal to the population one generation ago, so it’s “delayed” in some sense, but our intuition still tells us that this should be close to exponential. Of course, it isn’t actually exponential, otherwise the ratio would be constant. Nevertheless, the ratio approaches , commonly known as the golden ratio. That means that in the long run, behaves more or less like the function . However, we want an exact formula for , so let’s see how we go about finding that.
One way is by using generating functions. A generating function for a sequence is just a power series whose coefficients record information about that sequence, usually the actual numbers. For example, let’s take a look at our beloved sequence . The terms are 1, 2, 4, 8, 16, 32, and so on, so the generating function for the sequence is
where the coefficient of is simply . Notice that we can write more compactly. Since we know that , we have
Now, the function is pretty nice, and if we remember anything about infinite geometric series, then we know that if , then this function converges and we can write it as . But when we’re talking about generating functions, we don’t care about converging, so we can just say since
Now we notice that is just with replaced with , so we can write
Since we have in this nice form, we can expand it to get and find out that . Wait a minute. Didn’t we use the fact that to get the nice form? This is true, but there is another way to get the nice form of without knowing the explicit formula for , and it just involves a little algebraic trickery.
We know that . Therefore,
Furthermore, if we multiply by , we get a similarly looking thing:
In fact, what we have is
If we move all the terms involving to the left-hand side and factor out by , we get
from which it is easy to see that .
Now let’s try doing this with the generating function
and see what happens. Our recurrence relation means
which we can rearrange to get
We can use the quadratic formula to find the roots of which happen to be and . Therefore, we can write
Moreover, we can use partial fraction decomposition to write
To solve for and , we note that
which gives us the system of linear equations
Solving for yields
However, we want our denominators to be of the form , so that we can expand it into , so we rewrite
and finally we note that
Moreover, and . Let’s call these numbers and , respectively. Then what we have is
Therefore, we have just concluded that
Now that we have worked so hard to get this formula, let’s take a step back and appreciate it. This formula is useful in several ways. For starters, it allows us to compute much faster. For example, using the method of building up from all the previous terms, we have to do a linear number of operations, or in asymptotic notation. However, using the formula, we can compute and by repeatedly squaring and , which is logarithmic asymptotically, or . Furthermore, this formula shows us the exponential growth in . Not only that, it is crystal clear from this formula where the golden ratio comes from! Note that , so as gets large, the term becomes negligible, which is why for large , is approximately .
To recap, from this post you should have learned the following:
- What generating functions are and how they can be used to find closed formulae for sequences given by linear recurrences
- What the Fibonacci numbers are and how they arise in nature
- How to find a closed formula for the Fibonacci numbers using generating functions
- Why knowing the closed formula allows us to compute terms faster
- How the closed formula for the Fibonacci numbers sheds light on its growth rate and where the golden ratio comes about