Generating functions — an introduction
A generating function packs a sequence into a power series: A(x) = Σaₙxⁿ. The point is that natural operations on sequences become algebra on functions — shifting is multiplying by x, and convolution becomes multiplication. Solving a recurrence then reduces to solving a linear equation for A(x) and expanding it back with partial fractions.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Define A(x) = ΣaₙxⁿFix whether the sum starts at n = 0 or n = 1 and stay consistent.
- Translate the recurrenceMultiply the recurrence by xⁿ and sum, expressing every shifted sum in terms of A(x).
- Solve for A(x)The result is usually a rational function of x.
- Expand to read off coefficientsUse partial fractions and the geometric series 1/(1−ax) = Σaⁿxⁿ.
Worked example
Use generating functions to solve aₙ = 2aₙ₋₁ with a₀ = 1.
- Let A(x) = Σ_{n≥0} aₙxⁿ.
- Multiply the recurrence by xⁿ and sum for n ≥ 1: A(x) − a₀ = 2x·A(x).
- So A(x)(1 − 2x) = 1, giving A(x) = 1/(1 − 2x).
- Expand geometrically: 1/(1−2x) = Σ2ⁿxⁿ.
Answer. aₙ = 2ⁿ, read directly off the coefficient of xⁿ.
Where marks get dropped
These are the specific errors that cost credit on generating functions — an introduction questions — QED's rubric penalises each of them separately.
- Forgetting the initial term when shifting sums. Σ_{n≥1}aₙxⁿ is A(x) − a₀, not A(x).
- Worrying about convergence. In combinatorics these are formal power series, and convergence is irrelevant to coefficient extraction.
- Expanding without partial fractions when the denominator factors — the partial fraction step is what makes the coefficients readable.
Practise this until it is automatic
Unlimited fresh questions
QED generates new generating functions — an introduction problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Combinatorics mastery is tracked so you know when this is exam-ready.
Generating functions — an introduction — frequently asked questions
What is the key generating function to know?
1/(1−x) = Σxⁿ, and its variants 1/(1−ax) = Σaⁿxⁿ and 1/(1−x)^k = ΣC(n+k−1,k−1)xⁿ. Most exam problems reduce to these.
Why does convolution matter?
Because the coefficient of xⁿ in A(x)B(x) is Σaₖbₙ₋ₖ, exactly the convolution. Structures built by splitting an object into two parts give a product of generating functions.
What is an exponential generating function?
Σaₙxⁿ/n!, used when order within the objects matters — labelled structures such as permutations and set partitions.
The rest of Combinatorics
Counting principles, permutations, combinations. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Sum & product rules
- 2Permutations & combinations
- 3Binomial theorem & Pascal’s triangle
- 4The pigeonhole principle
- 5Inclusion–exclusion
- 6Counting with repetition (stars & bars)
- 7Derangements & counting surjections
- 8Double counting & bijective proofs
- 9Setting up & solving counting recurrences
- 10Generating functions — an introduction
- 11Multinomial coefficients & repeated items
- 12Hockey stick & Vandermonde identities
- 13Catalan numbers & lattice-path counting
Ready to make generating functions — an introduction exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →