Key takeaways
- The generating function of a sequence a₀, a₁, a₂, … is A(x) = a₀ + a₁x + a₂x² + ⋯; the sequence is stored in the coefficients.
- The basic identity is 1/(1 − x) = 1 + x + x² + ⋯, and 1/(1 − cx) generates 1, c, c², ….
- Multiplying generating functions combines choices: the coefficient of xⁿ in a product counts the ways to split n between the factors.
- To solve a recurrence, multiply it by xⁿ, sum, solve for A(x), then use partial fractions to read off the coefficients.
- The variable x is a placeholder: treated as a formal power series, the generating function needs no convergence for counting.
A generating function is a way of writing down an infinite sequence as a single object you can do algebra with. The sequence a₀, a₁, a₂, … becomes the power series
A(x) = a₀ + a₁x + a₂x² + a₃x³ + ⋯
The powers of x are only labels: the coefficient of xⁿ is the nth term. Once a sequence is packaged this way, adding, multiplying and simplifying the series answers questions about the sequence, including counting problems and recurrences that are awkward to attack directly. Levin's Discrete Mathematics: An Open Introduction covers building generating functions, manipulating them and using them to solve recurrence relations, which is the route followed here.
The one identity everything starts from
The geometric series gives
1/(1 − x) = 1 + x + x² + x³ + ⋯,
the generating function of 1, 1, 1, 1, …. Every other basic generating function comes from it.
| Generating function | Sequence | How |
|---|---|---|
| 1/(1 − x) | 1, 1, 1, 1, … | Geometric series |
| 1/(1 − 2x) | 1, 2, 4, 8, … | Replace x by 2x |
| 1/(1 + x) | 1, −1, 1, −1, … | Replace x by −x |
| x/(1 − x) | 0, 1, 1, 1, … | Multiply by x: shift right |
| 1/(1 − x)² | 1, 2, 3, 4, … | Differentiate 1/(1 − x) |
| (1 + x)ⁿ | C(n, 0), C(n, 1), …, C(n, n) | Binomial theorem |
| 1/(1 − x)ᵏ | C(n + k − 1, k − 1) for n = 0, 1, … | Stars and bars |
Two operations are worth naming. Multiplying by x shifts the sequence one place to the right. Multiplying by 1/(1 − x) takes partial sums: the coefficient of xⁿ in A(x)/(1 − x) is a₀ + a₁ + ⋯ + aₙ.
The last row is the stars and bars count, and the sixth is the binomial theorem seen from a new angle.
Counting with products
Multiplying generating functions combines independent choices. The coefficient of xⁿ in A(x)B(x) is
a₀bₙ + a₁bₙ₋₁ + ⋯ + aₙb₀,
the number of ways to split a total of n between the two choices.
Example: making change. In how many ways can you make 10 cents from 1-cent, 2-cent and 5-cent coins? Each coin type contributes a factor listing how much value it can supply:
- 1-cent coins: 1 + x + x² + x³ + ⋯ = 1/(1 − x)
- 2-cent coins: 1 + x² + x⁴ + ⋯ = 1/(1 − x²)
- 5-cent coins: 1 + x⁵ + x¹⁰ + ⋯ = 1/(1 − x⁵)
The answer is the coefficient of x¹⁰ in 1/((1 − x)(1 − x²)(1 − x⁵)). Expanding by hand is easiest by sorting on the number of 5-cent coins: with none, 0 to 5 two-cent coins, 6 ways; with one, 0 to 2 two-cent coins, 3 ways; with two, 1 way. Total: 10.
The generating function earns its keep when the questions change. Restrictions become changes to the factors: "at most three 2-cent coins" replaces 1/(1 − x²) with 1 + x² + x⁴ + x⁶, and the same product machinery handles it.
Solving a recurrence
Take the Tower of Hanoi recurrence aₙ = 2aₙ₋₁ + 1 with a₀ = 0.
Step 1: multiply by xⁿ and sum over n ≥ 1:
Σ aₙxⁿ = 2 Σ aₙ₋₁xⁿ + Σ xⁿ.
Step 2: rewrite each sum in terms of A(x). The left side is A(x) − a₀ = A(x). The first sum on the right is 2x·A(x). The last is x/(1 − x). So
A(x) = 2x·A(x) + x/(1 − x).
Step 3: solve for A(x):
A(x) = x/((1 − x)(1 − 2x)).
Step 4: partial fractions. Write x/((1 − x)(1 − 2x)) = P/(1 − x) + Q/(1 − 2x). Then x = P(1 − 2x) + Q(1 − x). Putting x = 1 gives P = −1; putting x = 1/2 gives Q = 1. So
A(x) = 1/(1 − 2x) − 1/(1 − x).
Step 5: read off coefficients. The coefficient of xⁿ is 2ⁿ − 1. So aₙ = 2ⁿ − 1, the same answer as the characteristic-root method in recurrence relations.
For this recurrence the characteristic method is quicker. Generating functions win when the recurrence is harder: when the extra term is a more complicated function of n, or when it is a convolution such as the one that defines the Catalan numbers, Cₙ₊₁ = Σ CᵢCₙ₋ᵢ, which turns into a quadratic equation for the generating function.
Do we need the series to converge?
For counting, no. MathWorld defines a generating function as a formal power series whose coefficients give the sequence, and in that formal setting x is a placeholder, not a number to substitute. The identities above hold as statements about coefficients. Analytic questions only matter when you want to estimate how fast the coefficients grow.
A short practice set
- Find the sequence generated by 1/(1 − 3x). (1, 3, 9, 27, …)
- Find the generating function for 0, 1, 2, 3, …. (x/(1 − x)².)
- Use a product of three factors to count solutions of a + b + c = 6 with a ≤ 2 and b, c unrestricted. (The coefficient of x⁶ in (1 + x + x²)/(1 − x)², which is 7 + 6 + 5 = 18.)
- Solve aₙ = 3aₙ₋₁ with a₀ = 2 using generating functions. (A(x) = 2/(1 − 3x), so aₙ = 2·3ⁿ.)
Sums written with sigma notation, used throughout this guide, are covered in summation notation. Recurrences have their own unit in Discrete Math: Study & Quiz, the ninth, between probability and graph theory. It is in our education app collection; the discrete math hub collects the related counting guides.
Good to know
Frequently asked questions
What is a generating function?
What is the generating function for 1, 1, 1, …?
How do generating functions solve recurrence relations?
Why does multiplying generating functions count combinations?
Sources
- Generating Functions (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed
- Generating Function (opens in a new tab)Wolfram MathWorld — accessed
About the author
Reign Creative LLC — The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.
We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.
No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.
Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.