Solving Recurrences Using Generating Functions
Combinatorics – IMO Preparation
1. Simple Explanation
A recurrence relation gives a sequence (a_n) in terms of its previous terms.
Generating functions translate the sequence into a formal power series
[ A(x)=\sum_{n\ge 0} a_n x^n . ]
Operations on the series (multiplication, differentiation, etc.) correspond to shifts and linear combinations of the terms of the sequence.
Thus, a recurrence can often be turned into an algebraic equation for (A(x)), solved, and then expanded back to obtain (a_n).
2. Key Points
| Item | What It Means | Why It Matters |
|---|---|---|
| Ordinary Generating Function (OGF) | (A(x)=\sum_{n\ge 0} a_n x^n) | Handles sequences indexed by (n). |
| Shift property | (\sum_{n\ge 0} a_{n+k}x^n = \frac{A(x)-a_0-a_1x-\dots-a_{k-1}x^{k-1}}{x^k}) | Turns (a_{n+k}) into a rational function of (A(x)). |
| Linear recurrence | (a_n = c_1 a_{n-1} + \dots + c_k a_{n-k}) | Leads to a linear equation in (A(x)). |
| Multiplication by (x) | (xA(x)=\sum_{n\ge 0} a_n x^{n+1}) | Moves the index up by 1. |
| Solving for (A(x)) | Usually yields (A(x)=\frac{P(x)}{Q(x)}) | (Q(x)) reflects the characteristic polynomial. |
| Partial fractions / series expansion | Decompose (A(x)) to read off (a_n) | Gives explicit formula for (a_n). |
| Radius of convergence | Relevant for analytic aspects, but not needed for IMO | Keeps in mind that we work formally. |
| Combinatorial interpretation | Often (a_n) counts objects; generating function encodes their weighted count | Helps to guess the form of (A(x)). |
3. Worked Example
Problem
Find a closed formula for the sequence defined by
[ a_0 = 1,\qquad a_1 = 1,\qquad a_n = a_{n-1} + 2 a_{n-2}\quad (n\ge 2). ]
Step 1: Write the OGF
[ A(x)=\sum_{n\ge 0} a_n x^n. ]
Step 2: Express shifted sums
[ \sum_{n\ge 2} a_{n-1}x^n = x \sum_{m\ge 1} a_m x^{m} = x(A(x)-a_0) = x(A(x)-1), ]
[ \sum_{n\ge 2} a_{n-2}x^n = x^2 \sum_{m\ge 0} a_m x^{m} = x^2 A(x). ]
Step 3: Translate the recurrence
Multiply the recurrence by (x^n) and sum for (n\ge 2):
[ \sum_{n\ge 2} a_n x^n = \sum_{n\ge 2} a_{n-1}x^n + 2\sum_{n\ge 2} a_{n-2}x^n. ]
Left side is (A(x) - a_0 - a_1 x = A(x)-1-x).
Plug the shifted sums:
[ A(x)-1-x = x(A(x)-1) + 2x^2 A(x). ]
Step 4: Solve for (A(x))
[ A(x)-1-x = xA(x)-x + 2x^2 A(x) ]
[ A(x) - xA(x) - 2x^2 A(x) = 1 - x. ]
Factor (A(x)):
[ A(x)\bigl(1 - x - 2x^2\bigr) = 1 - x. ]
[ \boxed{A(x)=\frac{1-x}{1 - x - 2x^2}}. ]
Step 5: Partial‑fraction / closed form
Factor the denominator:
[ 1 - x - 2x^2 = (1-2x)(1+x). ]
So
[ A(x)=\frac{1-x}{(1-2x)(1+x)}. ]
Decompose:
[ A(x)=\frac{A}{1-2x} + \frac{B}{1+x}. ]
Solve for (A,B):
[ 1-x = A(1+x)+B(1-2x). ]
Set (x=1): (0 = A(2)+B(-1) \Rightarrow 2A - B = 0).
Set (x=-1): (2 = A(0)+B(3) \Rightarrow 3B=2 \Rightarrow B=\frac{2}{3}).
Then (A = \frac{B}{2} = \frac{1}{3}).
Hence
[ A(x)=\frac{1}{3}\frac{1}{1-2x} + \frac{2}{3}\frac{1}{1+x}. ]
Now expand each as a geometric series:
[ \frac{1}{1-2x} = \sum_{n\ge 0} (2x)^n = \sum_{n\ge 0} 2^n x^n, ] [ \frac{1}{1+x} = \sum_{n\ge 0} (-1)^n x^n. ]
Thus
[ A(x)=\sum_{n\ge 0}\left(\frac{1}{3}2^n + \frac{2}{3}(-1)^n\right)x^n. ]
Therefore the closed form for the sequence is
[ \boxed{a_n = \frac{2^n + 2(-1)^n}{3}}. ]
Check:
(n=0): ((1+2)/3=1).
(n=1): ((2-2)/3=0) (oops! Mistake; recalc).
Wait, we mis‑solved B. Let's recompute