Generating Functions for Sequences
(A concise study guide for the IMO Algebra syllabus)
1. Simple Explanation
A generating function is a formal power series that encodes an infinite sequence
[
a_0,a_1,a_2,\dots
]
in a single algebraic object.
Ordinary generating function (OGF)
[
A(x)=\sum_{n=0}^{\infty} a_n,x^n .
]
Why use it?
- It turns problems about sequences (recurrences, combinatorics) into problems in algebra (polynomials, rational functions).
- Operations on sequences translate to algebraic manipulations (addition → series addition, convolution → product, etc.).
2. Key Points
| Topic | What to remember |
|---|---|
| Definition | (A(x)=\sum_{n\ge0} a_nx^n). Treat as a formal series (no convergence needed). |
| OGF vs EGF | Ordinary OGF for “plain” combinatorial data. Exponential GFs (E(x)=\sum a_n x^n/n!) are useful when order matters (permutations). |
| Basic Operations | • (x^k A(x)) shifts the sequence: coefficients of (x^n) become (a_{n-k}). • (A(x)+B(x)) → term‑wise addition. • (A(x)B(x)) → convolution: coefficient of (x^n) is (\sum_{k=0}^n a_k b_{n-k}). |
| Recurrences | Linear recurrences with constant coefficients lead to rational generating functions. Example: (a_{n}=c_1a_{n-1}+c_2a_{n-2}) → (A(x)=\frac{P(x)}{1-c_1x-c_2x^2}). |
| Partial Fractions | Useful to extract explicit formulae for (a_n). |
| Common Sequences | 0‑th: (1/(1-x)) gives all 1’s. 1‑st: (x/(1-x)^2) gives (n). Geometric: (1/(1-ax)) gives (a^n). Fibonacci: (\frac{x}{1-x-x^2}). |
| Combinatorial Identities | Generating functions can prove binomial identities, sums, etc., by comparing coefficients. |
3. Worked Example – The Fibonacci Numbers
Problem: Find the ordinary generating function (F(x)) for the Fibonacci sequence (F_0=0,;F_1=1,;F_{n}=F_{n-1}+F_{n-2}) for (n\ge2).
Step 1: Write the definition
[ F(x)=\sum_{n=0}^{\infty}F_nx^n . ]
Step 2: Shift the series according to the recurrence
[ \begin{aligned} F(x) &= F_0 + F_1x + \sum_{n=2}^{\infty}F_nx^n \ &= 0 + x + \sum_{n=2}^{\infty}(F_{n-1}+F_{n-2})x^n \ &= x + \sum_{n=2}^{\infty}F_{n-1}x^n + \sum_{n=2}^{\infty}F_{n-2}x^n . \end{aligned} ]
Step 3: Re‑index the sums
[ \begin{aligned} \sum_{n=2}^{\infty}F_{n-1}x^n &= x\sum_{k=1}^{\infty}F_k x^k = x\bigl(F(x)-F_0\bigr)=xF(x),\[4pt] \sum_{n=2}^{\infty}F_{n-2}x^n &= x^2\sum_{k=0}^{\infty}F_k x^k = x^2F(x). \end{aligned} ]
Step 4: Assemble the equation
[ F(x)=x + xF(x) + x^2F(x). ]
Step 5: Solve for (F(x))
[ F(x)-xF(x)-x^2F(x)=x \quad\Longrightarrow\quad F(x)\bigl(1-x-x^2\bigr)=x \quad\Longrightarrow\quad F(x)=\frac{x}{1-x-x^2}. ]
Step 6: Extract an explicit formula (optional)
Factor the denominator: (1-x-x^2=(1-\alpha x)(1-\beta x)) where
(\alpha=\frac{1+\sqrt5}{2},;\beta=\frac{1-\sqrt5}{2}).
Partial fractions give
[
F(x)=\frac{1}{\sqrt5}\Bigl(\frac{1}{1-\alpha x}-\frac{1}{1-\beta x}\Bigr)
]
so that
[
F_n=\frac{\alpha^n-\beta^n}{\sqrt5},
]
the Binet formula.
4. Quick Revision Summary
| Concept | Formula / Idea | Example |
|---|---|---|
| OGF | (A(x)=\sum a_nx^n) | Sequence of all 1’s → (1/(1-x)) |
| Shift | (x^kA(x)) → (a_{n-k}) | (x^2A(x)) shifts two places |
| Product | Coefficient of (x^n) in (A(x)B(x)) = (\sum_{k=0}^n a_kb_{ |