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:

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

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

\frac{1}{1 - x} = 1 + x + x^2 + x^3 + \cdots

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:

(1 + 2x + 4x^2 + 8x^3) - (1 + x + x^2 + x^3) = x + 3x^2 + 7x^3

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

c_n = a_0 b_n + a_1 b_{n-1} + \cdots + a_n b_0

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

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

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

Generating series

a₀ + a₁x + a₂x² + …

The coefficient of xⁿ is aₙ.

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² + …)?

← Previous topicNext topic →