Contents
 Basics
 Some standard generating functions
 More operations on formal power series and generating functions
 Counting with generating functions
 Generating functions and recurrences
 Recovering coefficients from generating functions
 Asymptotic estimates
 Recovering the sum of all coefficients
 A recursive generating function
 Summary of operations on generating functions
 Variants
 Further reading
1. Basics
The short version: A generating function represents objects of weight n with z^{n}, and adds all the objects you have up to get a sum a_{0}z^{0} + a_{1}z^{1} + a_{2}z^{2} + ..., where each a_{n} counts the number of different objects of weight n. If you are very lucky (or constructed your set of objects by combining simpler sets of objects in certain straightforward ways) there will be some compact expression that is expands to this horrible sum but is easier to right down. Such compact expressions are called generating functions, and manipulating them algebraically gives an alternative to actually knowing HowToCount.
1.1. A simple example
We are given some initial prefixes for words: qu, s, and t; some vowels to put in the middle: a, i, and oi; and some suffixes: d, ff, and ck, and we want to calculate the number of words we can build of each length.
One way is to generate all 27 words^{1} and sort them by length:
sad sid tad tid quad quid sack saff sick siff soid tack taff tick tiff toid quack quaff quick quiff quoid soick soiff toick toiff quoick quoiff
This gives us 4 length3 words, 12 length4 words, 9 length5 words, and 2 length6 words. This is probably best done using a computer, and becomes expensive if we start looking at much larger lists.
An alternative is to solve the problem by judicious use of algebra. Pretend that each of our letters is actually a variable, and that when we concatenate qu, oi, and ck to make quoick, we are really multiplying the variables using our usual notation. Then we can express all 27 words as the product (qu+s+t)(a+i+oi)(d+ff+ck). But we don't care about the exact set of words, we just want to know how many we get of each length.
So now we do the magic trick: we replace every variable we've got with a single variable z. For example, this turns quoick into zzzzzz = z^{6}, so we can still find the length of a word by reading off the exponent on z. But we can also do this before we multiply everything out, getting
We can now read off the number of words of each length directly off the coefficients of this polynomial.
1.2. Why this works
In general, what we do is replace any object of weight 1 with z. If we have an object with weight n, we think of it as n weight1 objects stuck together, i.e., z^{n}. Disjoint unions are done using addition as in simple counting: z+z^{2} represents the choice between a weight1 object and a weight2 object (which may have been built out of 2 weight1 objects), while 12z^{4} represents a choice between 12 different weight4 objects. The trick is that when we multiply two expressions like this, whenever two values z^{k} and z^{l} collide, the exponents add to give a new value z^{k+l} representing a new object with total weight k+l, and if we have something more complex like (nz^{k})(mz^{l}), then the coefficient multiply to give (nm)z^{k+l} different weight (k+l) objects.
For example, suppose we want to count the number of robots we can build given 5 choices of heads, each of weight 2, and 6 choices of bodies, each of weight 5. We represent the heads by 5z^{2} and the bodies by 6z^{5}. When we multiply these expressions together, the coefficients multiply (which we want, by the product rule) and the exponents add: we get 5z^{2}⋅6z^{5} = 30z^{7} or 30 robots of weight 7 each.
The real power comes in when we consider objects of different weights. If we add to our 5 weight2 robot heads two extrafancy heads of weight 3, and compensate on the body side with three new lightweight weight4 bodies, our new expression is (5z^{2}+2z^{3})(3z^{4}+6z^{5}) = 15z^{6}+36z^{7}+12z^{8}, giving a possible 15 weight6 robots, 36 weight7 robots, and 12 weight8 robots. The rules for multiplying polynomials automatically tally up all the different cases for us.
This trick even works for infinitelylong polynomials that represent infinite series (such "polynomials" are called formal power series). Even though there might be infinitely many ways to pick three natural numbers, there are only finitely many ways to pick three natural numbers whose sum is 37. By computing an appropriate formal power series and extracting the coefficient from the z^{37} term, we can figure out exactly how many ways there are. This works best, of course, when we don't have to haul around an entire infinite series, but can instead represent it by some more compact function whose expansion gives the desired series. Such a function is called a generating function, and manipulating generating functions can be a powerful alternative to creativity in making combinatorial arguments.
1.3. Formal definition
Given a sequence a_{0},a_{1},a_{2},..., its generating function F(z) is given by the sum
A sum in this form is called a formal power series. It is "formal" in the sense that we don't necessarily plan to actually compute the sum, and are instead using the string of z^{i} terms as a long rack to store coefficients on.
In some cases, the sum has a more compact representation. For example, we have
so 1/(1z) is the generating function for the sequence 1,1,1,.... This may let us manipulate this sequence conveniently by manipulating the generating function.
Here's a simple case. If F(z) generates some sequence a_{i}, what does sequence b_{i} does F(2z) generate? The ith term in the expansion of F(2z) will be a_{i}(2z)^{i} = a_{i} 2^{i} z^{i}, so we have b_{i} = 2^{i} a_{i}. This means that the sequence 1,2,4,8,16,... has generating function 1/(12z). In general, if F(z) represents a_{i}, then F(cz) represents c^{i}a_{i}.
What else can we do to F? One useful operation is to take its derivative with respect to z. We then have
This almost gets us the representation for the series i a_{i}, but the exponents on the z's are off by one. But that's easily fixed:
So the sequence 0,1,2,3,4,... has generating function
and the sequence of squares 0,1,4,9,16,... has generating function
As you can see, some generating functions are prettier than others.
(We can also use integration to divide each term by i, but the details are messier.)
Another way to get the sequence 0,1,2,3,4,... is to observe that it satisfies the recurrence:
a_{0} = 0
a_{n+1} = a_{n} + 1 (∀n∈ℕ)
A standard trick in this case is to multiply each of the ∀i bits by z^{n}, sum over all n, and see what happens. This gives ∑ a_{n+1}z^{n} = ∑ a_{n}z^{n} + ∑ z^{n} = ∑ a_{n}z^{n} + 1/(1z). The first term on the righthand side is the generating function for a_{n}, which we can call F(z) so we don't have to keep writing it out. The second term is just the generating function for 1,1,1,1,1,... . But what about the lefthand side? This is almost the same as F(z), except the coefficients don't match up with the exponents. We can fix this by dividing F(z) by z, after carefully subtracting off the a_{0} term:
So this gives the equation (F(z)  a_{0})/z = F(z) + 1/(1z). Since a_{0} = 0, we can rewrite this as F(z)/z = F(z) + 1/(1z). A little bit of algebra turns this into F(z)  zF(z) = z/(1z) or F(z) = z/(1z)^{2}.
Yet another way to get this sequence is construct a collection of objects with a simple structure such that there are exactly n objects with weight n. One way to do this is to consider strings of the form a^{+}b^{*} where we have at least one a followed by zero or more b's. This gives n strings of length n, because we get one string for each of 1..n a's we can put in (an example would be abb, aab, and aaa for n=3). We can compute the generating function for this set because to generate each string we must pick in order:
 One initial a. Generating function = z.
 Zero or more a's. Generating function = 1/(1z).
 Zero or more b's. Generating function = 1/(1z).
Taking the product of these gives z/(1z)^{2}, as before.
This trick is useful in general; if you are given a generating function F(z) for a_{n}, but want a generating function for b_{n} = ∑_{k≤n} a_{k}, allow yourself to pad each weightk object out to weight n in exactly one way using nk junk objects, i.e. multiply F(z) by 1/(1z).
2. Some standard generating functions
Here is a table of some of the most useful generating functions.
Of these, the first is the most useful to remember (it's also handy for remembering how to sum geometric series). All of these equations can be proven using the binomial theorem.
3. More operations on formal power series and generating functions
Let F(z) = ∑_{i} a_{i}z^{i} and G(z) = ∑_{i} b_{i}z^{i}. Then their sum F(z)+G(z) = ∑_{i} (a_{i}+b_{i})z^{i} is the generating function for the sequence (a_{i}+b_{i}). What is their product F(z)G(z)?
To compute the ith term of F(z)G(z), we have to sum over all pairs of terms, one from F and one from G, that produce a z^{i} factor. Such pairs of terms are precisely those that have exponents that sum to i. So we have
As we've seen, this equation has a natural combinatorial interpretation. If we interpret the coefficient a_{i} on the ith term of F(z) as counting the number of "athings" of weight i, and the coefficient b_{i} as the number of "bthings" of weight i, then the ith coefficient of F(z)G(z) counts the number of ways to make a combined thing of total weight i by gluing together an athing and a bthing.
As a special case, if F(z)=G(z), then the ith coefficient of F(z)G(z) = F^{2}(z) counts how many ways to make a thing of total weight i using two "athings", and F^{n}(z) counts how many ways (for each i) to make a thing of total weight i using n "athings". This gives us an easy combinatorial proof of a special case of the binomial theorem:
Think of the lefthand side as the generating function F(x) = 1+x raised to the nth power. F by itself says that you have a choice between one weight0 object or one weight1 object. On the righthand side the ith coefficient counts how many ways you can put together a total of i weight1 objects given n to choose from—so it's n choose i.
4. Counting with generating functions
The product formula above suggests that generating functions can be used to count combinatorial objects that are built up out of other objects, where our goal is to count the number of objects of each possible nonnegative integer "weight" (we put "weight" in scare quotes because we can make the "weight" be any property of the object we like, as long as it's a nonnegative integer—a typical choice might be the size of a set, as in the binomial theorem example above). There are five basic operations involved in this process; we've seen two of them already, but will restate them here with the others.
Throughout this section, we assume that F(z) is the generating function counting objects in some set A and G(z) the generating function counting objects in some set B.
4.1. Disjoint union
Suppose C = A∪B and A and B are disjoint. Then the generating function for objects in C is F(z)+G(z).
Example: Suppose that A is the set of all strings of zero or more letters x, where the weight of a string is just its length. Then F(z) = 1/(1z), since there is exactly one string of each length and the coefficient a_{i} on each z^{i} is always 1. Suppose that B is the set of all strings of zero or more letters y and/or z, so that G(z) = 1/(12z) (since there are now 2^{i} choices of lengthi strings). The set C of strings that are either (a) all x's or (b) made up of y's, z's, or both, has generating function F(z)+G(z) = 1/(1z) + 1/(12z).
4.2. Cartesian product
Now let C = A×B, and let the weight of a pair (a,b)∈C be the sum of the weights of a and b. Then the generating function for objects in C is F(z)G(z).
Example: Let A be allx strings and B be all y or z strings, as in the previous example. Let C be the set of all strings that consist of zero or more x's followed by zero or more y's and/or z's. Then the generating function for C is F(z)G(z) = 1/((1z)(12z)).
4.3. Repetition
Now let C consists of all finite sequences of objects in A, with the weight of each sequence equal to the sum of the weights of its elements (0 for an empty sequence). Let H(z) be the generating function for C. From the preceding rules we have
H = 1 + F + F^{2} + F^{3} + ... = 1/(1F).
This works best when H(0) = 0; otherwise we get infinitely many weight0 sequences. It's also worth noting that this is just a special case of substitution (see below), where our "outer" generating function is 1/(1z).
4.3.1. Example: (011)*
Let A = { 0, 11 }, and let C be the set of all sequences of zeroes and ones where ones occur only in evenlength runs. Then the generating function for A is z+z^{2} and the generating function for C is 1/(1zz^{2}). We can extract exact coefficients from this generating function using the techniques below.
4.3.2. Example: sequences of positive integers
Suppose we want to know how many different ways there are to generate a particular integer as a sum of positive integers. For example, we can express 4 as 4, 3+1, 2+2, 2+1+1, 1+1+1+1, 1+1+2, 1+2+1, or 1+3, giving 8 different ways.
We can solve this problem using the repetition rule. Let F = z/(1z) generate all the positive integers. Then
We can get exact coefficients by observing that
This means that there is 1 way to express 0 (the empty sum), and 2^{n1} ways to express any larger value n (e.g. 2^{41} = 8 ways to express 4).
Once we know what the right answer is, it's not terribly hard to come up with a combinatorial explanation. The quantity 2^{n1} counts the number of subsets of an (n1)element set. So imagine that we have n1 places and we mark some subset of them, plus add an extra mark at the end; this might give us a pattern like XXX. Now for each sequence of places ending with a mark we replace it with the number of places (e.g. XXX = 1,1,2, XXXX = 1,3,2,4). Then the sum of the numbers we get is equal to n, because it's just counting the total length of the sequence by dividing it up at the marks and the adding the pieces back together. The value 0 doesn't fit this pattern (we can't put in the extra mark without getting a sequence of length 1), so we have 0 as a special case again.
If we are very clever, we might come up with this combinatorial explanation from the beginning. But the generating function approach saves us from having to be clever.
4.4. Pointing
This operation is a little tricky to describe. Suppose that we can think of each weightk object in A as consisting of k items, and that we want to count not only how many weightk objects there are, but how many ways we can produce a weightk object where one of its k items has a special mark on it. Since there are k different items to choose for each weightk object, we are effectively multiplying the count of weightk objects by k. In generating function terms, we have
 H(z) = z d/dz F(z).
Repeating this operation allows us to mark more items (with some items possibly getting more than one mark). If we want to mark n distinct items in each object (with distinguishable marks), we can compute
H(z) = z^{n} d^{n}/dz^{n} F(z),
where the repeated derivative turns each term a_{i} z^{i} into a_{i}i(i1)(i2)...(in+1) z^{in} and the z^{n} factor fixes up the exponents. To make the marks indistinguishable (i.e., we don't care what order the values are marked in), divide by n! to turn the extra factor into (i choose n).
(If you are not sure how to take a derivative, look at HowToDifferentiate.)
Example: Count the number of finite sequences of zeroes and ones where exactly two digits are underlined. The generating function for { 0, 1 } is 2z, so the generating function for sequences of zeros and ones is F = 1/(12z) by the repetition rule. To mark two digits with indistinguishable marks, we need to compute
4.5. Substitution
Suppose that the way to make a Cthing is to take a weightk Athing and attach to each its k items a Bthing, where the weight of the new Cthing is the sum of the weights of the Bthings. Then the generating function for C is the composition F(G(z)).
Why this works: suppose we just want to compute the number of Cthings of each weight that are made from some single specific weightk Athing. Then the generating function for this quantity is just (G(z))^{k}. If we expand our horizons to include all a_{k} weightk Athings, we have to multiply by a_{k} to get a_{k} (G(z))^{k}. If we further expand our horizons to include Athings of all different weights, we have to sum over all k:
But this is just what we get if we start with F(z) and substitute G(z) for each occurrence of z, i.e. if we compute F(G(z)).
4.5.1. Example: bitstrings with primes
Suppose we let A be all sequences of zeroes and ones, with generating function F(z) = 1/(12z). Now suppose we can attach a single or double prime to each 0 or 1, giving 0' or 0'' or 1' or 1'', and we want a generating function for the number of distinct primed bitstrings with n attached primes. The set { prime, primeprime } has generating function G(z)=z+z^{2}, so the composite set has generating function F(z) = 1/(12(z+z^{2})) = 1/(12z2z^{2}).
4.5.2. Example: (011)* again
The previous example is a bit contrived. Here's one that's a little more practical, although it involves a brief digression into multivariate generating functions. A multivariate generating function F(x,y) generates a series ∑_{ij} a_{ij} x^{i}y^{j}, where a_{ij} counts the number of things that have i x's and j y's. (There is also the obvious generalization to more than two variables). Consider the multivariate generating function for the set { 0, 1 }, where x counts zeroes and y counts ones: this is just x+y. The multivariate generating function for sequences of zeroes and ones is 1/(1xy) by the repetition rule. Now suppose that each 0 is left intact but each 1 is replaced by 11, and we want to count the total number of strings by length, using z as our series variable. So we substitute z for x and z^{2} (since each one turns into a string of length 2) for y, giving 1/(1zz^{2}). This gives another way to get the generating function for strings built by repeating 0 and 11.
5. Generating functions and recurrences
What makes generating functions particularly useful for algorithm analysis is that they directly solve recurrences of the form T(n) = a T(n1) + b T(n2) + f(n) (or similar recurrences with more T terms on the righthand side), provided we have a generating function F(z) for f(n). The idea is that there exists some generating function G(z) that describes the entire sequence of values T(0),T(1),T(2),..., and we just need to solve for it by restating the recurrence as an equation about G. The lefthand side will just turn into G. For the righthand side, we need to shift T(n1) and T(n2) to line up right, so that the righthand side will correctly represent the sequence T(0),T(1),aT(0)+aT(1)+F(2), etc. It's not hard to see that the generating function for the sequence 0,T(0),T(1),T(2),... (corresponding to the T(n1) term) is just zG(z), and similarly the sequence 0,0,T(1),T(2),T(3),... (corresponding to the T(n2) term) is z^{2}G(z). So we have (being very careful to subtract out extraneous terms at for i=0 and i=1):
G = az(G  T(0)) + bz^{2}G + (F  f(0)  zf(1)) + T(0) + zT(1),
and after expanding F we can in principle solve this for G as a function of z.
5.1. Example: A Fibonaccilike recurrence
Let's take a concrete example. The Fibonaccilike recurrence
 T(n) = T(n1) + T(n2), T(0) = 1, T(1) = 1,
becomes
G = (zG  z) + z^{2}G + 1 + z.
(here F = 0).
Solving for G gives
G = 1/(1  z  z^{2}).
Unfortunately this is not something we recognize from our table, although it has shown up in a couple of examples. (Exercise: Why does the recurrence T(n) = T(n1) + T(n2) count the number of strings built from 0 and 11 of length n?) In the next section we show how to recover a closedform expression for the coefficients of the resulting series.
6. Recovering coefficients from generating functions
There are basically three ways to recover coefficients from generating functions:
 Recognize the generating function from a table of known generating functions, or as a simple combination of such known generating functions. This doesn't work very often but it is possible to get lucky.
To find the kth coefficient of F(z), compute the kth derivative d^{k}/dz^{k} F(z) and divide by k! to shift a_{k} to the z^{0} term. Then substitute 0 for z. For example, if F(z) = 1/(1z) then a_{0} = 1 (no differentiating), a_{1} = 1/(10)^{2} = 1, a_{2} = 1/(10)^{3} = 1, etc. This usually only works if the derivatives have a particularly nice form or if you only care about the first couple of coefficients (it's particularly effective if you only want a_{0}).
If the generating function is of the form 1/Q(z), where Q is a polynomial with Q(0)≠0, then it is generally possible to expand the generating function out as a sum of terms of the form P_{c}/(1z/c) where c is a root of Q (i.e. a value such that Q(c) = 0). Each denominator P_{c} will be a constant if c is not a repeated root; if c is a repeated root, then P_{c} can be a polynomial of degree up to one less than the multiplicity of c. We like these expanded solutions because we recognize 1/(1z/c) = ∑_{i} c^{i} z^{i}, and so we can read off the coefficients a_{i} generated by 1/Q(z) as an appropriately weighted some of c_{1}^{i}, c_{2}^{i}, etc., where the c_{j} range over the roots of Q.
Example: Take the generating function G = 1/(1zz^{2}). We can simplify it by factoring the denominator: 1zz^{2} = (1az)(1bz) where 1/a and 1/b are the solutions to the equation 1zz^{2}=0; in this case a = (1+√5)/2, which is approximately 1.618 and b = (1√5)/2, which is approximately 0.618. It happens to be the case that we can always expand 1/P(z) as A/(1az) + B(1bz) for some constants A and B whenever P is a degree 2 polynomial with constant coefficient 1 and distinct roots a and b, so
 G = A/(1az) + B/(1bz),
and here we can recognize the righthand side as the sum of the generating functions for the sequences A⋅a^{i} and B⋅b^{i}. The A⋅a^{i} term dominates, so we have that T(n) = Theta(a^{n}), where a is approximately 1.618. We can also solve for A and B exactly to find an exact solution if desired.
A rule of thumb that applies to recurrences of the form T(n) = a_{1}T(n1) + a_{2}T(n2) + ... a_{k} T(nk) + f(n) is that unless f is particularly large, the solution is usually exponential in 1/x, where x is the smallest root of the polynomial 1  a_{1}z  a_{2}z^{2} ...  a_{k} z^{k}. This can be used to get very quick estimates of the solutions to such recurrences (which can then be proved without fooling around with generating functions).
Exercise: What is the exact solution if T(n) = T(n1) + T(n2) + 1? Or if T(n) = T(n1) + T(n2) + n?
6.1. Partial fraction expansion and Heaviside's coverup method
There is a nice trick for finding the numerators in a partial fraction expansion. Suppose we have
Multiply both sides by 1az to get
Now plug in z = 1/a to get
We can immediately read off A. Similarly, multiplying by 1bz and then setting 1bz to zero gets B. The method is known as the "coverup method" because multiplication by (1az) can be simulated by covering up (1az) in the denominator of the lefthand side and all the terms that don't have (1az) in the denominator in the right hand side.
The coverup method will work in general whenever there are no repeated roots, even if there are many of them; the idea is that setting 1qz to zero knocks out all the terms on the righthand side but one. With repeated roots we have to worry about getting numerators that aren't just a constant, so things get more complicated. We'll come back to this case below.
6.1.1. Example: A simple recurrence
Suppose f(0) = 0, f(1) = 1, and for n≥2, f(n) = f(n1) + 2f(n2). Multiplying these equations by z^{n} and summing over all n gives a generating function
With a bit of tweaking, we can get rid of the sums on the RHS by converting them into copies of F:
Now solve for F(z) to get , where we need to solve for A and B.
We can do this directly, or we can use the coverup method. The coverup method is easier. Setting z = 1 and covering up 1+z gives A = 1/(12(1)) = 1/3. Setting z = 1/2 and covering up 12z gives B = 1/(1+z) = 1/(1+1/2) = 2/3. So we have
So we have f(0) = 0 and, for n≥1, . It's not hard to check that this gives the same answer as the recurrence.
6.1.2. Example: Coughing cows
Let's count the number of strings of each length of the form (M)*(OU)*(GHK)* where (xy) means we can use x or y and * means we can repeat the previous parenthesized expression 0 or more times (see Regular_expression).
We start with a sequence of 0 or more M's. The generating function for this part is our old friend 1/(1z). For the second part, we have two choices for each letter, giving 1/(12z). For the third part, we have 1/(13z). Since each part can be chosen independently of the other two, the generating function for all three parts together is just the product:
Let's use the coverup method to convert this to a sum of partial fractions. We have
So the exact number of lengthn sequences is (1/2)  4⋅2^{n} + (9/2)⋅3^{n}. We can check this for small n:
n 
Formula 
Strings 
0 
1/2  4 + 9/2 = 1 
() 
1 
1/2  8 + 27/2 = 6 
M, O, U, G, H, K 
2 
1/2  16 + 81/2 = 25 
MM, MO, MU, MG, MH, MK, OO, OU, OG, OH, OK, UO, UU, UG, UH, UK, GG, GH, GK, HG, HH, HK, KG, KH, KK 
3 
1/2  32 + 243/2 = 90 
(exercise) ☺ 
6.1.3. Example: A messy recurrence
Let's try to solve the recurrence T(n) = 4T(n1) + 12T(n2) + 1 with T(0) = 0 and T(1) = 1.
Let F = ∑ T(n)z^{n}.
Summing over all n gives
Solving for F then gives
We want to solve this using partial fractions, so we need to factor (14z12z²) = (1+2z)(16z). This gives
From this we can immediately read off the value of T(n) for n≥2:
Let's check this against the solutions we get from the recurrence itself:
n 
T(n) 
0 
0 
1 
1 
2 
1+4⋅1+12⋅0 = 5 
3 
1+4⋅5+12⋅1 = 33 
4 
1+4⋅33+12⋅5 = 193 
We'll try n=3, and get T(3) = (3/20)⋅216 + 8/12  1/15 = (3⋅3⋅216 + 40  4)/60 = (1944 + 40  4)/60 = 1980/60 = 33.
To be extra safe, let's try T(2) = (3/20)⋅36  4/12  1/15 = (3⋅3⋅36  20  4)/60 = (324  20  4)/60 = 300/60 = 5. This looks good too.
The moral of this exercise? Generating functions can solve uglylooking recurrences exactly, but you have to be very very careful in doing the math.
6.2. Partial fraction expansion with repeated roots
Let a_{n} = 2a_{n1} + n, with some constant a_{0}. Find a closedform formula for a_{n}.
As a test, let's figure out the first few terms of the sequence:
a_{0} = a_{0} 
a_{1} = 2a_{0} + 1 
a_{2} = 4a_{0} + 2 + 2 = 4a_{0}+4 
a_{3} = 8a_{0} + 8 + 3 = 8a_{0}+11 
a_{4} = 16a_{0} + 22 + 4 = 16a_{0}+26 
The a_{0} terms look nice (they're 2^{n}a_{0}), but the 0, 1, 4, 11, 26 sequence doesn't look like anything familiar. So we'll find the formula the hard way.
First we convert the recurrence into an equation over generating functions and solve for the generating function F:
Observe that the righthand term gives us exactly the 2^{n}a_{0} terms we expected, since 1/(12z) generates the sequence 2^{n}. But what about the lefthand term? Here we need to apply a partialfraction expansion, which is simplified because we already know how to factor the denominator but is complicated because there is a repeated root.
We can now proceed in one of two ways: we can solve directly for the partial fraction expansion, or we can use an extended version of Heaviside's coverup method that handles repeated roots using differentiation. We'll start with the direct method.
6.2.1. Solving for the PFE directly
Write
We expect B to be a constant and A to be of the form A_{1}z + A_{0}.
To find B, use the technique of multiplying by 12z and setting z=1/2:
so B = 1/(11/2)^{2} = 1/(1/4) = 4.
We can't do this for A, but we can solve for it after substituting in B = 4:
So we have the expansion
from which we get
If we remember that 1/(1z)^{2} generates the sequence x_{n} = n+1 and 1/(12z) generates x_{n} = 2^{n}, then we can quickly read off the solution (for large n):
which we can check by plugging in particular values of n and comparing it to the values we got by iterating the recurrence before.
The reason for the "large n" caveat is that z^{2}/(1z)^{2} doesn't generate precisely the sequence x_{n} = n1, since it takes on the values 0, 0, 1, 2, 3, 4, ... instead of 1, 0, 1, 2, 3, 4, ... . Similarly, the power series for z/(12z) does not have the coefficient 2^{n1} = 1/2 when n = 0. Miraculously, in this particular example the formula works for n = 0, even though it shouldn't: 2(n1) is 2 instead of 0, but 4·2^{n1} is 2 instead of 0, and the two errors cancel each other out.
6.2.2. Solving for the PFE using the extended coverup method
It is also possible to extend the coverup method to handle repeated roots. Here we choose a slightly different form of the partial fraction expansion:
Here A, B, and C are all constants. We can get A and C by the coverup method, where for A we multiply both sides by (1z)² before setting z=1; this gives A = 1/(12) = 1 and C = 1/(1½)² = 4. For B, if we multiply both sides by (1z) we are left with A/(1z) on the righthand side and a (1z) in the denominator on the lefthand side. Clearly setting z = 1 in this case will not help us.
The solution is to first multiply by (1z)² as before but then take a derivative:
Now if we set z = 1, every term on the righthand side except B becomes 0, and we get B = 2/(12)² or B = 2.
Plugging A, B, and C into our original formula then gives
and thus
From this we can read off (for large n):
We believe this because it looks like the solution we already got.
7. Asymptotic estimates
We can simplify our life considerably if we only want an asymptotic estimate of a_{n} (see AsymptoticNotation). The basic idea is that if a_{n} is nonnegative for sufficiently large n and ∑ a_{n}z^{n} converges for some fixed value z, then a_{n} must be o(z^{n}) in the limit. (Proof: otherwise, a_{n}z^{n} is at least a constant for infinitely many n, giving a divergent sum.) So we can use the radius of convergence of a generating function F(z), defined as the largest value r such that F(z) is defined for all (complex) z with z < r, to get a quick estimate of the growth rate of F's coefficients: whatever they do, we have a_{n} = O(r^{n}).
For generating functions that are rational functions (ratios of polynomials), we can use the partial fraction expansion to do even better. First observe that for F(z) = ∑ f_{i}z^{n} = 1/(1az)^{k}, we have f_{n} = (k+n1 choose n) a^{n} = ((n+k1),,(k1)/(k1)!) a^{n} = Θ(a^{n} n^{k1}). Second, observe that the denominator is irrelevant: if 1/(1az)^{k} = Θ(a^{n} n^{k1}) then bz^{m}/(1az)^{k1} = b Θ(a^{nm} (nm)^{k1}) = b a^{m} (1m/n)^{k1} Θ(a^{n} n^{k1}) = Θ(a^{n} n^{k1}), because everything outside the Θ disappears into the constant for sufficiently large n. Finally, observe that in a partial fraction expansion, the term 1/(1az)^{k} with the largest coefficient a (if there is one) wins in the resulting asymptotic sum: Θ(a^{n}) + Θ(b^{n}) = Θ(a^{n}) if a > b. So we have:
 Theorem
Let F(z) = ∑ f_{n}z^{n} = P(z)/Q(z) where P and Q are polynomials in z. If Q has a root r with multiplicity k, and all other roots s of Q satisfy r < s, then f_{n} = Θ((1/r)^{n} n^{k1}).
The requirement that r is a unique minimal root of Q is necessary; for example, F(z) = 2/(1z²) = 1/(1z) + 1/(1+z) generates the sequence 0, 2, 0, 2, ..., which is not Θ(1) because of all the zeros; here the problem is that 1z² has two roots with the same absolute value, so for some values of n it is possible for them to cancel each other out.
A root in the denominator of a rational function F is called a pole. So another way to state the theorem is that the asymptotic value of the coefficients of a rational generating function is determined by the smallest pole.
More examples:
F(z) 
Smallest pole 
Asymptotic value 
1/(1z) 
1 
Θ(1) 
1/(1z)² 
1, multiplicity 2 
Θ(n) 
1/(1zz²) 
(√51)/2 = 2/(1+√5) 
Θ(((1+√5)/2)^{n}) 
1/((1z)(12z)(13z)) 
1/3 
Θ(3^{n}) 
(z+z²(1z))/(14z12z²) 
1/6 
Θ(6^{n}) 
1/((1z)²(12z)) 
1/2 
Θ(2^{n}) 
In each case it may be instructive to compare the asymptotic values to the exact values obtained earlier on this page.
8. Recovering the sum of all coefficients
Given a generating function for a convergent series ∑_{i} a_{i}z^{i}, we can compute the sum of all the a_{i} by setting z to 1. Unfortunately, for many common generating functions setting z=1 yields 0/0 (if it yields something else divided by zero then the series diverges). In this case we can recover the correct sum by taking the limit as z goes to 1 using L'Hôpital's_rule, which says that lim_{x→c} f(x)/g(x) = lim_{x→c} f'(x)/g'(x) when the latter limit exists and either f(c) = g(c) = 0 or f(c) = g(c) = infinity.^{2}
8.1. Example
Let's derive the formula for 1+2+...+n. We'll start with the generating function for the series ∑_{i=0}^{n} z^{i}, which is (1z^n+1)/(1z). Applying the z d/dz method gives us
Plugging z=1 into this expression gives (1(n+1)+n)/(11) = 0/0, which does not make us happy. So we go to the hospital—twice, since one application of L'Hôpital's rule doesn't get rid of our 0/0 problem:
which is our usual formula. Gauss's childhood proof is a lot quicker, but the generatingfunction proof is something that we could in principle automate most of the work using a computer_algebra_system, and it doesn't require much creativity or intelligence. So it might be the weapon of choice for nastier problems where no clever proof comes to mind.
More examples of this technique can be found on the BinomialCoefficients page, where the binomial theorem applied to (1+x)^{n} (which is really just a generating function for ∑ (n choose i) z^{i}) is used to add up various sums of binomial coefficients.
9. A recursive generating function
Let's suppose we want to count binary trees with n internal nodes. We can obtain such a tree either by (a) choosing an empty tree (g.f.: z^{0} = 1); or (b) choosing a root with weight 1 (g.f. 1⋅z^{1} = z, since we can choose it in exactly one way), and two subtrees (g.f. = F^{2} where F is the g.f. for trees). This gives us a recursive definition
F = 1 + zF^{2}.
Solving for F using the quadratic formula gives
That 2z in the denominator may cause us trouble later, but let's worry about that when the time comes. First we need to figure out how to extract coefficients from the square root term.
The binomial theorem says
For n ≥ 1, we can expand out the (1/2 choose n) terms as
For n=0, the switch from the big product of odd terms to (2n2)! divided by the even terms doesn't work, because (2n2)! is undefined. So here we just use the special case (1/2 choose 0) = 1.
Now plug this nasty expression back into F to get
Here we choose minus for the plusorminus to get the right answer and then do a little bit of tidying up of the binomial coefficient.
We can check the first few values of f(n):
n 
f(n) 
0 
(0 choose 0) = 1 
1 
(1/2)(2 choose 1) = 1 
2 
(1/3)(4 choose 2) = 6/3 = 2 
3 
(1/4)(6 choose 3) = 20/4 = 5 
and these are consistent with what we get if we draw all the small binary trees by hand.
The numbers (1/(n+1))(2n choose n) show up in a lot of places in combinatorics, and are known as the Catalan_numbers.
10. Summary of operations on generating functions
The following table describes all the nasty things we can do to a generating function. Throughout, we assume F = ∑ f_{k}z^{k}, G = ∑ g_{k}z^{k}, etc.
Operation 
Effect on generating functions 
Effect on coefficients 
Combinatorial interpretation 
Coefficient extraction 
f_{k} = (1/k!) d^{k}/dz^{k} F(z) _{z=0} 

Find the number of weight k objects. Easy case: f_{0} = F(0). 
Sum of all coefficients 
F(1) 
Computes ∑ f_{k} 
Count the total number of objects, ignoring weights. 
Shift right 
G = zF 
g_{k} = f_{k1} 
Add 1 to the weight of all objects. 
Shift left 
G = z^{1}(FF(0)) 
g_{k} = f_{k+1} 
Subtract 1 from the weight of all objects. 
Pointing 
G = z d/dz F 
g_{k} = k f_{k} 
A Gthing is an Fthing plus a label pointing to one of its units. 
Sum 
H = F+G 
h_{k}=f_{k}+g_{k} 
Every Hthing is either an Fthing or a Gthing (think union) 
Product 
H=FG 
h_{k} = ∑_{i} f_{i}g_{ki} 
Every Hthing consists of an Fthing a Gthing (think cartesian product), with the weight of the Hthing equal to the sum of the weights of the F and G things. 
Composition 
H=F∘G 
H = ∑ f_{k}G^{k} 
To make an Hthing, first choose an Fthing of weight m, then bolt onto it m Gthings. The weight of the Hthing is the sum of the weights of the Gthings. 
Repetition 
G=1/(1F) 
G = ∑ F^{k} 
A Gthing is a sequence of zero or more Fthings. Note: this is just a special case of composition. 
11. Variants
The exponential generating function or egf for a sequence a_{0}, ... is given by F(z) = ∑ a_{n}z^{n}/n!. For example, the egf for the sequence 1, 1, 1, ... is e^{z} = ∑ z^n/n!. Exponential generating functions admit a slightly different set of operations from ordinary generating functions: differentation gives left shift (since the factorials compensate for the exponents coming down), multiplying by z gives b_{n} = na_{n+1}, etc. The main application is that the product F(z)G(z) of two egf's gives the sequence whose nth term is ∑ (n choose k) a_{k}b_{nk}; so for problems where we want that binomial coefficient in the convolution (e.g. when we are building weight n objects not only by choosing a weightk object plus a weight(nk) object but also by arbitrarily rearranging their unitweight pieces) we want to use an egf rather than an ogf. We won't use these in CS202, but it's worth knowing they exist.
A probability generating function or pgf is essentially an ordinary generating function where each coefficient a_{n} is the probability that some random variable equals n. See RandomVariables for more details.
12. Further reading
RosenBook discusses some basic facts about generating functions in §7.4. ConcreteMathematics gives a more thorough introduction. Herbert Wilf's book generatingfunctionology, which can be downloaded from the web, will tell you more about the subject than you probably want to know.
See http://www.swarthmore.edu/NatSci/echeeve1/Ref/LPSA/PartialFraction/PartialFraction.html for very detailed notes on partial fraction expansion.
CategoryAlgorithmNotes CategoryMathNotes
We are using word in the combinatorial sense of a finite sequence of letters (possibly even the empty sequence) and not the usual sense of a finite, nonempty sequence of letters that actually make sense. (1)
The justification for doing this is that we know that a finite sequence really has a finite sum, so the "singularity" appearing at z=1 in e.g. (1z^{n+1})/(1z) is an artifact of the generatingfunction representation rather than the original series—it's a removable_singularity that can be replaced by the limit of f(x)/g(x) as x→c. (2)