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 F_0,F_1, F_2, F_3, F_4, \ldots, defined by

F_0 = 0 \\ F_1 = 1 \\ F_n = F_{n-1} + F_{n-2}, n \ge 1,

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 n is P_n, then P_n = P_{n-1} + P_{n-2}, since on the previous day there are P_{n-1} cells but only P_{n-2} 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 F_n, so that if we wanted to find F_n, we don’t have to start from F_0 and build our way up. For example, if we had a sequence G_n defined by G_0 = 1 and G_n = G_{n-1} + G_{n-1}, 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 G_n = 2^n.

Intuitively, things whose growth rate is related to their current size grow exponentially. For example, the growth rate for our G_n is \Delta G_n = G_n - G_{n-1} = G_{n-1}, that is, the amount G_n 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 \Delta F_n = F_n - F_{n-1} = F_{n-2}, 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 \frac{F_n}{F_{n-1}} would be constant. Nevertheless, the ratio \frac{F_n}{F_{n-1}} approaches \phi = 1.6180339885\ldots, commonly known as the golden ratio. That means that in the long run, F_n behaves more or less like the function f(n) = \phi^n. However, we want an exact formula for F_n, 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 G_n = 2^n. The terms are 1, 2, 4, 8, 16, 32, and so on, so the generating function for the sequence is

G(x) = 1 + 2x + 4x^2 + 8x^3 + 16x^4 + 32x^5 + \cdots

where the coefficient of x^n is simply G_n. Notice that we can write G(x) more compactly. Since we know that G_n = 2^n, we have

G(x) = 1 + 2x + 2^2x^2 + 2^3x^3 + 2^4x^4 + \cdots = 1 + (2x) + (2x)^2 + (2x)^3 + (2x)^4 + \cdots.

Now, the function H(x) = 1 + x + x^2 + x^3 + x^4 + \cdots is pretty nice, and if we remember anything about infinite geometric series, then we know that if |x| < 1, then this function converges and we can write it as H(x) = \frac{1}{1-x}. But when we’re talking about generating functions, we don’t care about converging, so we can just say H(x) = \frac{1}{1-x} since

(1-x)H(x) = (1-x)(1 + x + x^2 + x^3 + \cdots) \\ = (1 + x + x^2 + x^3 + \cdots ) - (x + x^2 + x^3 + x^4 + \cdots) = 1.

Now we notice that G(x) is just H(x) with x replaced with 2x, so we can write

G(x) = H(2x) = \frac{1}{1 - 2x}.

Since we have G(x) in this nice form, we can expand it to get G(x) = 1 + (2x) + (2x)^2 + (2x)^3 + \cdots and find out that G_n = 2^n. Wait a minute. Didn’t we use the fact that G_n = 2^n to get the nice form? This is true, but there is another way to get the nice form of G(x) without knowing the explicit formula for G_n, and it just involves a little algebraic trickery.

We know that G_n = 2G_{n-1}. Therefore,

G(x) = G_0 + G_1x + G_2x^2 + G_3x^3 + G_4x^4 + \cdots \\ = G_0 + 2G_0x + 2G_1x^2 + 2G_2x^3 + 2G_3x^4 + \cdots.

Furthermore, if we multiply G(x) by x, we get a similarly looking thing:

xG(x) = G_0x + G_1x^2 + G_2x^3 + G_3x^4 + \cdots.

In fact, what we have is

G(x) = 1 + 2xG(x).

If we move all the terms involving G(x) to the left-hand side and factor out by G(x), we get

G(x)(1 - 2x) = 1

from which it is easy to see that G(x) = \frac{1}{1-2x}.

Now let’s try doing this with the generating function

F(x) = F_0 + F_1x + F_2x^2 + F_3x^3 + \cdots = 0 + x + x^2 + 2x^3 + 3x^4 + 5x^5 + \cdots

and see what happens. Our recurrence relation F_n = F_{n-1} + F_{n-2} means

F(x) = F_0 + F_1x + (F_1 + F_0)x^2 + (F_2 + F_1)x^3 + (F_3 + F_2)x^4 + \cdots \\ = F_0(1 + x + x^2) + F_1(x + x^2 + x^3) + F_2(x^3 + x^4) + F_3(x^4 + x^5) + \cdots

meanwhile

xF(x) = F_0x + F_1x^2 + F_2x^3 + F_3x^4 + \cdots \\ x^2F(x) = F_0x^2 + F_1x^3 + F_2x^4 + F_3x^5 + \cdots

and so

F(x) = F_0 + F_1x + xF(x) + x^2F(x) = x + xF(x) + x^2F(x)

which we can rearrange to get

F(x)(1 - x - x^2) = x

and so

F(x) = \frac{x}{1 - x - x^2} = \frac{-x}{x^2 + x - 1}.

We can use the quadratic formula to find the roots of x^2 + x - 1 which happen to be \phi = \frac{-1 + \sqrt 5}{2} and \psi = \frac{-1 - \sqrt 5}{2}. Therefore, we can write

F(x) = \frac{-x}{(x - \alpha)(x - \beta)}.

Moreover, we can use partial fraction decomposition to write

F(x) = \frac{-x}{(x - \alpha)(x - \beta)} = \frac{A}{x - \alpha} + \frac{B}{x - \beta}.

To solve for A and B, we note that

\frac{A}{x - \alpha} + \frac{B}{x - \beta} = \frac{(A+B)x - A\beta - B\alpha}{x^2 + x - 1}

which gives us the system of linear equations

A+B = -1 \\ A\beta + B\alpha = 0.

Solving for A,B yields

A = \frac{\alpha}{\beta - \alpha} \\ B = \frac{\beta}{\alpha - \beta}.

However, we want our denominators to be of the form 1 - \alpha x, so that we can expand it into 1 + (\alpha x) + (\alpha x)^2 + \cdots, so we rewrite

\frac{A}{x - \alpha} = \frac{-A/\alpha}{1 - x/\alpha} \\ \frac{B}{x - \beta} = \frac{-B/\beta}{1 - x/\beta}

and finally we note that

-\frac{A}{\alpha} = \frac{1}{\alpha - \beta} = \frac{1}{\sqrt 5} \\ -\frac{B}{\beta} = \frac{1}{\beta - \alpha} = -\frac{1}{\sqrt 5}.

Moreover, \frac{1}{\alpha} = \frac{2}{-1 + \sqrt 5} = \frac{1 + \sqrt 5}{2} and \frac{1}{\beta} = \frac{2}{-1 - \sqrt 5} = \frac{1 - \sqrt 5}{2}. Let’s call these numbers \phi and \psi, respectively. Then what we have is

F(x) = \frac{1}{\sqrt 5}\left( \frac{1}{1 - \phi x} - \frac{1}{1 - \psi x} \right) \\ = \frac{1}{\sqrt 5}\left[ (1 + \phi x + \phi^2x^2 + \phi^3x^3 + \cdots) - (1 + \psi x + \psi^2 x^2 + \psi^3 x^3 + \cdots) \right] \\ = \frac{1}{\sqrt 5} \left[ (\phi - \psi)x + (\phi^2 - \psi^2)x^2 + (\phi^3 - \psi^3)x^3 + \cdots \right].

Therefore, we have just concluded that

F_n = \frac{\phi^n - \psi^n}{\sqrt 5} = \frac{1}{\sqrt 5} \left[ \left( \frac{1 + \sqrt 5}{2} \right)^n - \left( \frac{1 - \sqrt 5}{2} \right)^n \right].

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 F_n much faster. For example, using the method of building up F_n from all the previous terms, we have to do a linear number of operations, or O(n) in asymptotic notation. However, using the formula, we can compute \phi^n and \psi^n by repeatedly squaring \phi and \psi, which is logarithmic asymptotically, or O(\log n). Furthermore, this formula shows us the exponential growth in F_n. Not only that, it is crystal clear from this formula where the golden ratio comes from! Note that |\psi| < 1, so as n gets large, the \psi^n term becomes negligible, which is why for large n, F_n is approximately \frac{1}{\sqrt 5} \phi^n.

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
Advertisements