Generating functions
Introduction to ordinary generating functions: definitions, basic operations, solving linear recurrences, counting with product GFs, worked examples (recurrence solution, Fibonacci/Binet, combinations), common exam mistakes and quick checks.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Generating functions convert sequences into power-series objects so we can use algebra to solve counting problems and recurrence relations. Engineers use them when analysing discrete systems (e.g., counts of solutions, state counts in finite automata, probability distributions in algorithms) and when turning recurrences that model system behaviour into closed-form formulas.
Key ideas
Ordinary generating function (OGF): for a sequence (a_n){n>=0} the OGF is the formal power series G(x) = sum{n>=0} a_n x^n. Bold: every time you see a_n we mean the nth term of the sequence and G(x) is its OGF.
Coefficient extraction operator: write [x^n]F(x) to mean "the coefficient of x^n in the formal series F(x)". So a_n = [x^n]G(x).
Addition rule: if sequences a_n and b_n have OGFs A(x) and B(x), then the sequence (a_n + b_n) has OGF A(x) + B(x). This follows directly from termwise addition of series.
Multiplication (convolution) rule: the product C(x) = A(x)·B(x) corresponds to the sequence c_n = sum_{k=0..n} a_k b_{n-k} (this sum is called the convolution of the sequences). Exact statement: if A(x)=sum a_k x^k and B(x)=sum b_k x^k then A(x)B(x)=sum_{n>=0}(sum_{k=0}^{n} a_k b_{n-k}) x^n. Proof: multiply series and collect coefficients of x^n.
Shifting and multiplication by x: x·A(x) = sum_{n>=0} a_n x^{n+1} = sum_{n>=1} a_{n-1} x^n. Hence [x^n] x A(x) = a_{n-1} for n>=1 and 0 for n=0. This is the algebraic way to represent index shifts. More generally, x^k A(x) shifts by k: [x^n] x^k A(x) = a_{n-k} (with a_m=0 for m<0). Differentiation: A'(x) = sum_{n>=0} (n+1) a_{n+1} x^n, so [x^n]A'(x) = (n+1) a_{n+1}. Partial sums: A(x)/(1-x) generates prefix sums, [x^n] A(x)/(1-x) = sum_{j=0}^n a_j.
Solving linear recurrences with constant coefficients (common exam derivation): suppose a_n satisfies a linear recurrence with constant coefficients for n>=r: a_n + c_1 a_{n-1} + c_2 a_{n-2} + ... + c_r a_{n-r} = f_n, with given initial values a_0,...,a_{r-1}. Multiply both sides by x^n and sum n from r to infinity. Replace shifted sums using G(x) and initial terms (use the shift identity). Solve algebraically for G(x): Q(x)G(x) = (a polynomial in x from the initial terms) + F(x) - (f_0 + f_1 x + ... + f_{r-1} x^{r-1}), where Q(x)=1 + c_1 x + c_2 x^2 + ... + c_r x^r and F(x)=sum_{n>=0} f_n x^n; hence G(x) is rational in x if F(x) is rational. Then extract coefficients by partial fractions or other series expansion methods. This derivation assumes we work formally; if interpreting as analytic functions, require convergence in some radius.
Rational generating functions and closed forms: a rational OGF (ratio of polynomials) corresponds to sequences that satisfy linear recurrences with constant coefficients. Partial fraction decomposition of G(x) (over reals or complex) leads to closed-form expressions a_n = sum_i P_i(n) r_i^n, where the denominator factors as prod_i (1 - r_i x)^{m_i} and P_i(n) are polynomials of degree < m_i. Equivalently, r_i are the reciprocals of the zeros of the denominator of G(x).
Counting with product GFs: If you have independent choices whose counts are encoded by generating functions A(x), B(x), etc., then the combined system's OGF is the product A(x)B(x)... For example, unlimited use of a coin of value 1 (counting number of coins) gives GF 1 + x + x^2 + ... = 1/(1-x) (as a formal series). The coefficient [x^n] (1-x)^{-k} = C(n+k-1,n) counts number of k-tuples of nonnegative integers summing to n. Proof: expand (1-x)^{-k} via the negative-binomial (combinatorial) identity for integer k>0.
Exponential generating function (EGF): defined for sequence a_n by A*(x)=sum_{n>=0} a_n x^n / n!. EGFs are used when counting labelled structures (brief definition only); do not mix OGFs and EGFs: the multiplication rules differ. For EGFs, if A*(x) and B*(x) are EGFs of a_n and b_n, then the product encodes c_n = sum_{k=0}^n C(n,k) a_k b_{n-k}.
When an exam asks for diagrams: for product/convolution proofs, draw two horizontal rows of coefficients a_0 a_1 a_2 ... and b_0 b_1 b_2 ...; to illustrate convolution for c_3, draw all pairs (a_0,b_3),(a_1,b_2),(a_2,b_1),(a_3,b_0) and label that they sum to form c_3.
Formulas
G(x) = sum_{n>=0} a_n x^n — G(x) is the ordinary generating function of sequence a_n; a_n dimensionless; applies formally for sequences.
[x^n] G(x) = a_n — coefficient extraction operator; a_n is the coefficient of x^n in G(x).
A(x)+B(x) corresponds to sequence a_n + b_n — addition rule; applies for any sequences.
A(x)·B(x) = sum_{n>=0} (sum_{k=0..n} a_k b_{n-k}) x^n — product corresponds to convolution; applies for formal power series.
If a_n + c_1 a_{n-1} + ... + c_r a_{n-r} = f_n then G(x)·(1 + c_1 x + ... + c_r x^r) = P(x) + F(x) - (f_0 + f_1 x + ... + f_{r-1} x^{r-1}) — after summing and using initial conditions; here F(x)=sum_{n>=0} f_n x^n and P(x) is the polynomial from a_0..a_{r-1}. Applies to linear recurrences with constant coefficients.
(1-x)^{-k} = sum_{n>=0} C(n+k-1, n) x^n — combinatorial identity for integer k>=1; applies as formal power series.
Notes on units: coefficients are counts or numbers (dimensionless). x is an indeterminate (dimensionless). When interpreting as functions, units not applicable.
Worked examples
Example 1 — Solve a recurrence (non-homogeneous): Problem: a_n = 3 a_{n-1} + 2 for n>=1, with a_0 = 1. Find a_n. Solution steps:
- Define G(x) = sum_{n>=0} a_n x^n.
- Multiply recurrence by x^n and sum n>=1: sum_{n>=1} a_n x^n = 3 sum_{n>=1} a_{n-1} x^n + 2 sum_{n>=1} x^n.
- Left side = G(x) - a_0. Right: 3 x G(x) + 2 (x/(1-x)).
- Substitute a_0=1: G(x) - 1 = 3 x G(x) + 2 x/(1-x).
- Solve for G(x): G(x)(1 - 3x) = 1 + 2 x/(1-x).
- Bring to common denom: G(x) = ( (1-x) + 2x ) / ((1-3x)(1-x)) = (1 + x) / ((1-3x)(1-x)).
- Partial fractions: (1+x)/((1-3x)(1-x)) = A/(1-3x) + B/(1-x). Solve: 1 + x = A(1-x) + B(1-3x). Expand: 1 + x = (A + B) + (-A -3B) x. Match coefficients: constant: A + B = 1. x-coef: -A - 3B = 1. Solve: Add equations: (A+B) + (-A-3B) = 1 + 1 => -2B = 2 => B = -1. Then A = 2.
- So G(x) = 2/(1-3x) - 1/(1-x) = 2 sum (3^n x^n) - sum(x^n).
- Hence a_n = 2·3^n - 1. Final answer: a_n = 2·3^n - 1.
Example 2 — Fibonacci and Binet via GF: Problem: a_0=0, a_1=1 and a_n = a_{n-1} + a_{n-2} for n>=2. Find closed form. Solution outline:
- Let F(x) = sum_{n>=0} a_n x^n.
- Use shift identities: F(x) - a_0 - a_1 x = x(F(x) - a_0) + x^2 F(x). Substituting a_0=0,a_1=1: F(x) - x = x F(x) + x^2 F(x).
- Rearranged: F(x)(1 - x - x^2) = x, so F(x) = x/(1 - x - x^2).
- Denominator roots: r1 = (1 + sqrt(5))/2, r2 = (1 - sqrt(5))/2, but note these are roots of λ^2 - λ -1 =0. For partial fraction we write x/(1 - x - x^2) = C/(1 - r1 x) + D/(1 - r2 x).
- Solve for C,D (standard algebra) gives C = 1/sqrt(5), D = -1/sqrt(5).
- Expand: a_n = (1/sqrt(5)) r1^n - (1/sqrt(5)) r2^n. This is Binet's formula. Final answer: a_n = (r1^n - r2^n)/sqrt(5) where r1=(1+sqrt(5))/2 and r2=(1-sqrt(5))/2. (Reviewer: check algebra step for C and D signs; location: Example 2 derivation.)
Example 3 — Counting combinations with GF: Problem: number of nonnegative integer solutions to x1 + x2 + x3 = n. Solution:
- Each xi has GF 1 + x + x^2 + ... = 1/(1-x).
- Total GF = (1/(1-x))^3 = (1-x)^{-3}.
- Use formula (1-x)^{-k} = sum C(n+k-1, n) x^n with k=3, hence coefficient = C(n+2, n) = C(n+2, 2). Final: number of solutions = C(n+2, 2) = (n+2)(n+1)/2.
Common mistakes
- Incorrect convolution limits: the sum for coefficient c_n is k=0..n, not 1..n or other ranges (unless sequences start later).
- Algebra errors in partial fraction decomposition (solve constants carefully and check by recombining).
- Treating formal series as analytic functions without checking radius of convergence when required by the problem (in combinatorics you may often work formally; in analytic problems check convergence).
For your exam
Typical question types:
- Definitions and short notes: define generating function, formal power series, convolution, OGF vs EGF.
- Derivation: derive G(x) for a given recurrence and solve for a_n; show steps multiplying by x^n, shifting, substituting initials.
- Numericals: compute coefficients from product GFs (coins, compositions, partitions limited case).
- Proof/derivation: show product corresponds to convolution; expand and collect coefficients.
- Small programs/algorithms are rare for pure GF but you may be asked to compute coefficients by expansion.
What a full-marks answer includes:
- Precise definitions (bold terms), statement of assumptions (sequence starts at n=0, recurrence holds for n>=r), and each algebraic step shown.
- Correct handling of initial terms when shifting sums.
- Correct partial fractions or series expansions to extract coefficients; final answer boxed or clearly stated.
- If combinatorial, a short justification why product of GFs counts the combined choices.
Quick check
- Define the OGF for sequence a_n = 2^n. What is G(x)?
- If A(x) = 1/(1-x) and B(x) = 1/(1-x)^2, what is coefficient of x^3 in A(x)B(x)?
- For recurrence a_n = 2 a_{n-1} with a_0 = 5, find a_n by generating functions. Answers: 1) G(x) = sum_{n>=0} 2^n x^n = 1/(1-2x) (formal). 2) A(x)B(x) = (1-x)^{-3}, coefficient [x^3] = C(3+2,2)=C(5,2)=10. 3) a_n = 5·2^n.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?