Foxmaths! 2.0

January 8, 2008

Generating Functions

Filed under: Maths — Tags: , , , — Fox @ 9:36 pm

Generating Functions are a neat tool in the study of recursive sequences.

A generating function is a clothesline on which we hang up a sequence of numbers for display.
— Herbert Wilf, Generatingfunctionology (1994)

The idea is that, given a sequence of numbers a_0, a_1, a_2, ..., we want to examine functions of the following form.

f(x) = a_0 + a_1 x + a_2 x^2 + ... = \sum_{n = 0}^\infty a_n x^n

This is the so called ‘ordinary’ generating function. By examining properties of f(x), we can derive information about the formula for that sequence of numbers.

There are variants, such as, starting with a_1 instead of a_0,

f(x) = a_1 + \frac{a_2}{2^x} + \frac{a_3}{3^x} + ... = \sum_{n = 1}^\infty \frac{a_n}{n^x}

But, in general, the idea is that you string out the terms of your sequence as coefficients on an infinite power series of some variety. The question then is, what does the summation converge to? What information can we get from that function? What use is it? How does this relate to recursive sequences? And how do I make myself talk like this?

To begin with, a number of tools are needed. This also serves as a few good examples of generating functions. Consider the following…

\frac{1}{1-x} = 1 + x + x^2 + x^3 + ... = \sum_{n=0}^\infty x^n

This can be proved relatively nicely, like so.

f(x) = 1 + x + x^2 + x^3 + ...
f(x) = 1 + x*(1 + x + x^2 + ...)
f(x) = 1 + x*f(x)
f(x) = \frac{1}{1 - x}

So, given a sequence of 1’s, a_n = 1 for all n, the generating function of that sequence is \frac{1}{1 - x}.

Now, given a sequence, its power series, and its generating function, all the normal rules of series apply. For example, differentiate the power series, and it converges to the derivative of the generating function. And power series are incredibly easy to differentiate. They simply become the sum of the derivative of each term. So we get the following.

\frac{d}{dx} \frac{1}{1 - x} = \frac{d}{dx}( 1 + x + x^2 + x^3 ... )
\frac{1}{{(1 - x)}^2} = 1 + 2x + 3x^2 + 4x^3 + ...
\frac{1}{{(1 - x)}^2} = \sum_{n = 0}^\infty (n+1)x^n

And, pulling the sequence of coefficients off that power series, we find that the generating function for the sequence 1, 2, 3, …, or rather a_n = n is given by \frac{1}{{(1 - x)}^2}. In general, through similar turns of differentiation, integration, additions and combinations, etc, you can show pretty much across the board that for any sequence where a_n is defined as some polynomial of n, that the generating function is some variant on \frac{1}{1 - x}.

So, at this point, 412 words in, you’re probably thinking, ok Fox – what’s the big deal?

Well, suppose you start out with a recurrence relation. For example, let a_0 = 1 and define a_n as

a_n = 2*a_{n-1}

Now, this relation has a relatively straightforward solution, but we’re going to solve it using generating functions. First, define the generating function A(x) to be

A(x) = \sum_{n = 0}^\infty a_n x^n

Now, take the recurrence relation. To begin with, multiply each side by x^n. Note that this doesn’t change the validity of the equation.

a_n x^n = 2*a_{n-1} x^n

Now, this really defines an infinite set of equations, one for each possible value of n. What we’re going to do is to combine all of these equations into a single equation, by summing on each side of the equation for n. This will produce a new, valid equation, since it will be a combination of an infinite set of valid equations, defined by the above schema. Note we’re going to start summing on each side at n = 1, not n = 0. This prevents having to deal with a_{-1}.

\sum_{n = 1}^\infty a_n x^n = \sum_{n = 1}^\infty 2*a_{n-1} x^n

Notice then, that the left side of the equation is -almost- the definition of the generating function. It’s missing the one term when n = 0. That being so, we can substitute in and say, equivalently…

A(x) - a_0 x^0 = \sum_{n = 1}^\infty 2*a_{n-1} x^n

Note though that a_0 x^0 = 1. Then on the right side, notice that we can factor the summation in the following way.

A(x) - 1 = 2 x \sum_{n = 1}^\infty a_{n-1} x^{n-1}

Now, in the summation on the right, all references to n are of the form n-1. As such, we can adjust the starting index of n, giving

A(x) - 1 = 2 x \sum_{n = 0}^\infty a_n x^n

And now, quite clearly, the summation on the right is of the same form as the generating function. Which lets us do the following, and solve for A(x).

A(x) - 1 = 2 x A(x)
A(x) = \frac{1}{1 - 2x}

So now we have the generating function for our recursively defined sequence, and we’ve derived it strictly from information given by the recurrence relation. What of it? Notice though, that the form we have, \frac{1}{1 - 2x} is rather similar to something we just discussed, \frac{1}{1 - x}. Indeed, grabbing the power series for \frac{1}{1 - x} from our toolbag, we can say the following.

A(x) = \frac{1}{1 - (2x)} = 1 + (2x) + {(2x)}^2 + ... = \sum_{n = 0}^\infty {(2x)}^n

A(x) = \sum_{n = 0}^\infty 2^n x^n = \sum_{n = 0}^\infty a_n x^n

Equating coefficients on like powers of x, it is then clear that

a_n = 2^n

And we’ve solved for an explicit form of the recurrence relation, unwrapping the recursive definition.

Now, granted, this was a fairly simple example. You can almost solve this by inspection. But it serves as a good example of what you can do with these, I think. Given a recurrence relation, you can derive the form of the generating function. And from that, using known power series, other tricks, a little intuition, and maybe even some art, you can derive a non-recursive definition for your recursive sequence.

To close, I’d like to do another example, which I find quite neat. Again, relatively straightforward, but it shows a neat potential.

Suppose we have -two- recursively defined sequences, a_n, b_n. We’ll say that a_0 = 1, b_0 = 0. The recursion relations defining the sequences are

a_n = 2 a_{n-1} + b_{n-1}
b_n = a_{n-1} + 2 b_{n-1}

These two sequences are coupled, that is to say, defined in terms of each other. This makes unwrapping the recursion even more difficult than normal.

But let’s look at this from the perspective of generating functions. Of course, to begin with, we have our usual generating function definitions…

A(x) = \sum_{n = 0}^\infty a_n x^n, B(x) = \sum_{n = 0}^\infty b_n x^n

Now, looking at the recursion relations, we start as we did before, multiplying through by a power of x.

a_n x^n = 2 a_{n-1} x^n + b_{n-1} x^n
b_n x^n = a_{n-1} x^n + 2 b_{n-1} x^n

As before, this defines a set (two sets, really) of equations, indexed by values of n. We’re going to combine all of these equations into two equations by summing them across the values of n. Note that the lowest indexed reference to n is n-1, so we will start our summation at n = 1.

\sum_{n = 1}^\infty a_n x^n = \sum_{n = 1}^\infty 2 a_{n-1} x^n + \sum_{n = 1}^\infty b_{n-1} x^n
\sum_{n = 1}^\infty b_n x^n = \sum_{n = 1}^\infty a_{n-1} x^n + \sum_{n = 1}^\infty 2 b_{n-1} x^n

The trick is then to do what is necessary to be able to substitute in terms of A(x) and B(x) in place of the power series summations.

A(x) - a_0 x^0 = 2 x \sum_{n = 1}^\infty a_{n-1} x^{n-1} + x \sum_{n = 1}^\infty b_{n-1} x^{n-1}
B(x) - b_0 x^0 = x \sum_{n = 1}^\infty a_{n-1} x^{n-1} + 2 x \sum_{n = 1}^\infty b_{n-1} x^{n-1}

A(x) - 1 = 2 x \sum_{n = 0}^\infty a_n x^n + x \sum_{n = 0}^\infty b_n x^n
B(x) - 0 = x \sum_{n = 0}^\infty a_n x^n + 2 x \sum_{n = 0}^\infty b_n x^n

A(x) - 1 = 2 x A(x) + x B(x)
B(x) = x A(x) + 2 x B(x)

But now, we have a system of equations, 2 equations and 2 variables, which allows us to solve explicitly for A(x) and B(x). Leaving the mechanics of such an endeavor to the interested reader, the final solution you find is that

A(x) = \frac{1 - 2 x}{1 - 4 x + 3 x^2}
B(x) = \frac{x}{1 - 4 x + 3 x^2}

And those are the explicit forms of the generating functions for each sequence, completely uncoupled. It merely remains to derive the power series form of each function, and you will have effectively unraveled the recursion relations. And this is doable without too much effort…

Note that 1 - 4 x + 3 x^2 = (1 - x)*(1 - 3 x). That being so, using partial fractions, we can expand A(x) and B(x) in the following way.

A(x) = \frac{1 - 2 x}{1 - 4 x + 3 x^2} = \frac{1/2}{1 - x} + \frac{1/2}{1 - 3x}

B(x) = \frac{x}{1 - 4 x + 3 x^2} = \frac{-1/2}{1 - x} + \frac{1/2}{1 - 3x}

Having that expanded form of A(x) and B(x), we can now jump back into our toolbox same way we did before…

A(x) = (1/2)* \frac{1}{1 - x} + (1/2)*\frac{1}{1 - 3x}
A(x) = (1/2) \sum_{n = 0}^\infty x^n + (1/2) \sum_{n = 0}^\infty {(3x)}^n
A(x) = (1/2) \sum_{n = 0}^\infty {(1 + 3^n)} x^n

A(x) = \sum_{n = 0}^\infty \frac{(1 + 3^n)}{2} x^n

From that form of A(x), we see that

a_n = \frac{3^n + 1}{2}

Similarly, for B(x),

B(x) = (-1/2)*\frac{1}{1 - x} + (1/2)*\frac{1}{1 - 3x}
B(x) = (-1/2) \sum_{n = 0}^\infty x^n + (1/2) \sum_{n = 0}^\infty {(3x)}^n
B(x) = (1/2) \sum_{n = 0}^\infty {(3^n - 1)} x^n

B(x) = \sum_{n = 0}^\infty \frac{(3^n - 1)}{2} x^n

And we get, looking at the formula for the coefficients of the series, that

b_n = \frac{(3^n - 1)}{2}

And there you have it. From the initial coupled equation, using generating functions we were, in relatively short order, able to pull the recursion apart and solve explicitly for the terms of both sequences.

The examples I present here are relatively simple, but the concepts can be broadly applied. Generating functions seem quite powerful, in the way that they take effectively an entire sequence, and compress it into one easily manageable form. It takes the relations between each individual element and the rest, and unifies them into one grand structure. It’s really rather neat.

So, generating functions : ) As usual, if you have any questions, feel free to ask.

5 Comments »

  1. [...] You’re Doing It Wrong!Mathematicians Are Best!What Is Math? (Baby Don’t Hurt Me, No More)Generating FunctionsCalculus and Geometry: A Family of EllipsesRamsey, Parties, and The Probabilistic MethodPrime [...]

    Pingback by Linear Recurrences And … Stuff « Foxmaths! 2.0 — July 26, 2008 @ 7:11 pm

    Reply

  2. [...] with which they seem to crop up. Fortunately, this one in particular seems to avoid the hassle of generating functions, and can be solved, fairly slickly, through pure [...]

    Pingback by Counting Ring Colorings « Foxmaths! 2.0 — August 2, 2008 @ 5:58 pm

    Reply

  3. What am I missing? Take x = 5.
    Are we saying 1/1-x = 1/1-5 = -1/4 = 1+x+x^2+x^3+… = infinity?

    ????? Thanks for any hints
    mike

    Comment by mike — August 4, 2008 @ 6:22 pm

    Reply

  4. Hi Mike!

    Sorry about that – my fault for not being clear and careful.

    The summation 1 + x + x^2 + .. = 1/(1 – x) only works if x is between 1 and -1.

    Different series converge for different ranges of x. For example, the sum of x^n/n! for n from 0 to infinity converges for all values of x.

    Comment by Fox — August 4, 2008 @ 6:39 pm

    Reply

  5. But the point of generating functions is not what the value of the generating function is at certain points, but what the -form- of the generating function is, and thus the form of the summation that converges to that.

    Comment by Fox — August 4, 2008 @ 6:46 pm

    Reply

RSS feed for comments on this post. TrackBack URI

Leave a comment

Blog at WordPress.com.