Discrete Math › Section G · Additional topics › Topic G.1
Generating functions
A generating function packs an entire infinite sequence into one algebraic expression by using the terms as coefficients of powers of x. Ordinary algebra on that expression, such as adding, multiplying and solving, then becomes a way to handle sequences, solve recurrences and count.
A clothesline for a sequence
Write a sequence \(a_0, a_1, a_2, \ldots\) as the coefficients of an infinite polynomial:
This is the generating series of the sequence, and each power of \(x\) acts as a peg labelling the position of the term hung on it. The series \(2 + 5x^2 - x^3\) generates 2, 0, 5, \(-1\), 0, 0, …: the coefficient of \(x^1\) is 0, so \(a_1 = 0\), not 5. When a series has a compact closed form, that expression is called the generating function. Sequences start at \(a_0\) here, matching the earlier topics of this course.
Formal series: x is only a placeholder
In calculus, for example in the calculus topic "Power series", the main question about a series is where it converges. Here we treat series formally: we never substitute a number for \(x\), and \(x\) only marks positions. What matters is that addition, multiplication and differentiation work term by term, exactly as for polynomials. Whenever a closed form like \(\frac{1}{1-x}\) is written for a series, it means that multiplying the series by \(1 - x\) gives exactly 1, coefficient by coefficient. That identity is all the later cards use.
The basic generating function
The simplest sequence, 1, 1, 1, …, has generating series \(S = 1 + x + x^2 + \cdots\). The multiply, shift and subtract method from "Exponential sequences and solving recurrences" applies: \(xS = x + x^2 + \cdots\), and subtracting leaves \((1 - x)S = 1\). So
Almost every other generating function in this topic is built from this one. Substituting \(-x\) for \(x\) gives \(\frac{1}{1 + x}\), which generates 1, \(-1\), 1, \(-1\), …; substituting \(3x\) gives \(\frac{1}{1 - 3x}\), which generates the powers of 3.
Building new generating functions
Four simple moves cover a great deal. Scaling: multiplying by a constant multiplies every term, so \(\frac{5}{1 - 2x}\) generates \(5 \cdot 2^n\). Substitution: replacing \(x\) by \(x^2\) in \(\frac{1}{1-x}\) gives \(\frac{1}{1 - x^2}\), which generates 1, 0, 1, 0, …. Adding: adding generating functions adds sequences term by term. Shifting: multiplying by \(x\) moves every term one place right and puts a 0 in front, so \(\frac{x^2}{1 - x}\) generates 0, 0, 1, 1, 1, …. Combining these handles any sequence built from geometric pieces.
Worked example: finding a generating function
Find the generating function of \(a_n = 2^n - 1\), the sequence 0, 1, 3, 7, 15, …. 1. Split the sequence: it is the powers of 2 minus the all-ones sequence. 2. The powers of 2 have generating function \(\frac{1}{1 - 2x}\), and 1, 1, 1, … has \(\frac{1}{1 - x}\). 3. Subtract: \(A(x) = \frac{1}{1 - 2x} - \frac{1}{1 - x}\). 4. Over a common denominator, \(A(x) = \frac{x}{(1 - x)(1 - 2x)}\). 5. Check by expanding the first terms:
giving 0, 1, 3, 7, as required.
Differentiating to get n
Differentiating \(1 + x + x^2 + x^3 + \cdots\) term by term gives \(1 + 2x + 3x^2 + \cdots\), while differentiating \(\frac{1}{1 - x}\) gives \(\frac{1}{(1 - x)^2}\). So \(\frac{1}{(1 - x)^2}\) generates 1, 2, 3, 4, …, and multiplying by \(x\) shifts it to \(\frac{x}{(1 - x)^2}\), which generates 0, 1, 2, 3, …, the sequence \(a_n = n\). Differentiating again shows that \(\frac{1}{(1 - x)^3}\) generates 1, 3, 6, 10, 15, …, the triangular numbers starting from 1. Each further derivative raises the degree of the polynomial pattern by one, the same pattern seen in "Polynomial sequences".
Multiplying generating functions
Multiply \(A(x) = \sum a_n x^n\) by \(B(x) = \sum b_n x^n\) and collect powers. The coefficient of \(x^n\) in the product is
called the convolution of the two sequences. The special case \(B(x) = \frac{1}{1 - x}\), with every \(b_n = 1\), gives \(c_n = a_0 + a_1 + \cdots + a_n\): multiplying by \(\frac{1}{1 - x}\) turns a sequence into its partial sums, and multiplying by \(1 - x\) turns it into its differences. For instance, \(\frac{1}{(1-x)^2} \cdot \frac{1}{1-x}\) gives the partial sums of 1, 2, 3, …, which are 1, 3, 6, 10.
Worked example: solving a recurrence
Solve \(a_n = 5a_{n-1} - 6a_{n-2}\) with \(a_0 = 1\) and \(a_1 = 4\). 1. Form \(A - 5xA + 6x^2A\). For \(n \ge 2\) the coefficient of \(x^n\) is \(a_n - 5a_{n-1} + 6a_{n-2} = 0\), leaving \(a_0 + (a_1 - 5a_0)x = 1 - x\). 2. So \(A(x) = \frac{1 - x}{(1 - 2x)(1 - 3x)}\). 3. Partial fractions: \(1 - x = P(1 - 3x) + Q(1 - 2x)\). Putting \(x = \frac{1}{2}\) gives \(P = -1\); putting \(x = \frac{1}{3}\) gives \(Q = 2\). 4. So \(A = \frac{2}{1 - 3x} - \frac{1}{1 - 2x}\), and \(a_n = 2 \cdot 3^n - 2^n\). 5. Check: \(a_2 = 20 - 6 = 14\), and \(18 - 4 = 14\). The characteristic root technique agrees.
Generating functions for counting
Products of generating functions also count combinations directly. In how many ways can you pay \(n\) cents with 1-cent and 2-cent coins? The 1-cent coins contribute \(1 + x + x^2 + \cdots\), where the exponent records how many cents they pay, and the 2-cent coins contribute \(1 + x^2 + x^4 + \cdots\). Each way to pay \(n\) cents picks one term from each factor with exponents adding to \(n\), so the answer is the coefficient of \(x^n\) in
For 5 cents it is 3: using zero, one or two 2-cent coins.
Common mistakes to avoid
First, misreading positions: the coefficient of \(x^n\) is \(a_n\), and a missing power means a zero term. Second, substituting numbers for \(x\); the series are formal. Third, forgetting the leftover initial terms when clearing a recurrence: \(A - 5xA + 6x^2A\) is \(1 - x\) here, not 0 and not 1. Fourth, mixing up \(\frac{1}{(1-x)^2}\), which generates 1, 2, 3, …, with \(\frac{x}{(1-x)^2}\), which generates 0, 1, 2, …. Fifth, multiplying sequences term by term: the product of generating functions is a convolution, not \(a_n b_n\).
Key takeaways
The generating function of \(a_0, a_1, \ldots\) is \(\sum a_n x^n\), treated as a formal series. Start from \(\frac{1}{1-x} = 1 + x + x^2 + \cdots\) and build others by scaling, substituting, adding, shifting by \(x\) and differentiating. Multiplying gives convolutions; multiplying by \(\frac{1}{1-x}\) gives partial sums. A linear recurrence turns into an equation for \(A(x)\), and partial fractions recover a closed formula. Products of simple series also count combinations, such as ways to make change.
Flashcards
Flashcard
a₀ + a₁x + a₂x² + …
Test your understanding
Question 1 of 5
Which sequence does the generating function 1/(1 − 3x) generate?
Question 2 of 5
Which generating function produces the sequence 0, 0, 1, 1, 1, 1, …?
Question 3 of 5
What is the coefficient of x⁴ in 1/(1 − x)²?
Question 4 of 5
Multiplying the generating function of a sequence by 1/(1 − x) produces the generating function of which sequence?
Question 5 of 5
What is the coefficient of x² in (1 + 2x + 3x² + …)(1 + x + x² + …)?
