Chapter: Generating Functions
Welcome to Generating Functions! While this might sound like an abstract topic, it is actually one of the most elegant and powerful tools in Discrete Mathematics. Mathematician Herbert Wilf famously described a generating function as "a clothesline on which we hang up a sequence of numbers for display."
Instead of juggling an endless list of individual numbers in a sequence, we pack the entire sequence into a single, compact algebraic expression (like a polynomial or a fraction). Once packed, we can use simple high-school algebra to solve complex counting problems and recurrence relations!
Don't worry if this seems unusual at first. We will break down every concept step-by-step with clear examples.
---1. What is an Ordinary Generating Function (OGF)?
Let \(\{u_r\} = (u_0, u_1, u_2, u_3, \dots)\) be a sequence of real numbers.
The ordinary generating function for this sequence is the formal power series defined by:
\(G(x) = \sum_{r=0}^{\infty} u_r x^r = u_0 + u_1 x + u_2 x^2 + u_3 x^3 + \dots\)
Here, the variable \(x\) acts merely as a placeholder or a "tag". The power \(x^r\) simply tells you the position of the term, and the coefficient of \(x^r\) is the actual value of the \(r^{\text{th}}\) term in your sequence, \(u_r\).
An Intuitive Analogy
Think of \(x\) as labeled coat hangers in a wardrobe:
• The \(x^0\) hanger holds \(u_0\)
• The \(x^1\) hanger holds \(u_1\)
• The \(x^2\) hanger holds \(u_2\)
• The \(x^r\) hanger holds \(u_r\)
We do not normally plug numbers into \(x\); instead, we manipulate the algebraic function to find the coefficients.
Key Takeaway
Key Takeaway: The coefficient of \(x^r\) in the expansion of \(G(x)\) is the sequence term \(u_r\). We write this mathematically as \(u_r = [x^r]G(x)\).
---2. The Essential Toolkit of Standard Generating Functions
To succeed in your exam, you need to recognize how standard sequences convert into compact closed forms (and vice versa). Most of these come directly from the Geometric Series and the Binomial Theorem.
1. The Constant Sequence: \((1, 1, 1, 1, \dots)\)
Sequence: \(u_r = 1\) for all \(r \ge 0\).
\(G(x) = 1 + x + x^2 + x^3 + \dots\)
Using the sum of an infinite geometric series \(S_{\infty} = \frac{a}{1-r}\) (for \(|x| < 1\)):
\(G(x) = \frac{1}{1 - x}\)
2. Geometric Sequence: \((1, a, a^2, a^3, \dots)\)
Sequence: \(u_r = a^r\) for \(r \ge 0\).
\(G(x) = 1 + ax + a^2 x^2 + a^3 x^3 + \dots = \frac{1}{1 - ax}\)
3. The Sequence of Counting Numbers: \((1, 2, 3, 4, \dots)\)
Sequence: \(u_r = r + 1\) for \(r \ge 0\).
\(G(x) = 1 + 2x + 3x^2 + 4x^3 + \dots = \frac{1}{(1 - x)^2}\)
4. The General Negative Binomial Series
For any positive integer \(n\):
\(\frac{1}{(1 - x)^n} = (1 - x)^{-n} = \sum_{r=0}^{\infty} \binom{n + r - 1}{r} x^r\)
Quick Memory Aid: The coefficient of \(x^r\) in \((1 - x)^{-n}\) is \(\binom{n + r - 1}{r}\) or \(\binom{n + r - 1}{n - 1}\).
5. Finite Sequences via the Binomial Theorem
For a positive integer \(n\):
\((1 + x)^n = \binom{n}{0} + \binom{n}{1}x + \binom{n}{2}x^2 + \dots + \binom{n}{n}x^n\)
This generates the finite sequence of binomial coefficients \(\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}\).
Quick Review Box: Common Closed Forms
• Sequence \((1, 1, 1, 1, \dots) \iff \frac{1}{1-x}\)
• Sequence \((1, 2, 4, 8, \dots) \iff \frac{1}{1-2x}\)
• Sequence \((1, -1, 1, -1, \dots) \iff \frac{1}{1+x}\)
• Sequence \((1, 2, 3, 4, \dots) \iff \frac{1}{(1-x)^2}\)
• Sequence \((1, 3, 6, 10, \dots) \iff \frac{1}{(1-x)^3}\) where \(u_r = \binom{r+2}{2} = \frac{(r+1)(r+2)}{2}\)
3. Algebraic Operations on Generating Functions
Just like standard polynomials, we can add, scale, shift, and multiply generating functions.
1. Addition (Sum Rule)
If \(A(x)\) generates \(\{a_r\}\) and \(B(x)\) generates \(\{b_r\}\), then:
\(A(x) + B(x)\) generates the term-by-term sum \(\{a_r + b_r\}\).
2. Scalar Multiplication
\(c \cdot A(x)\) generates the sequence \(\{c \cdot a_r\}\).
3. Shifting / Delaying a Sequence
Multiplying a generating function by \(x^k\) shifts the sequence to the right by \(k\) positions and inserts \(k\) zeros at the start:
\(x^k A(x) = a_0 x^k + a_1 x^{k+1} + a_2 x^{k+2} + \dots\)
The new sequence is \((0, 0, \dots, 0, a_0, a_1, a_2, \dots)\).
4. Convolution (Multiplying Two Generating Functions)
When you multiply \(A(x) \times B(x)\), what is the coefficient of \(x^r\)?
\((a_0 + a_1 x + a_2 x^2 + \dots)(b_0 + b_1 x + b_2 x^2 + \dots)\)
To get terms of degree \(r\), we pair terms whose powers add to \(r\):
\([x^r](A(x)B(x)) = a_0 b_r + a_1 b_{r-1} + a_2 b_{r-2} + \dots + a_r b_0 = \sum_{k=0}^{r} a_k b_{r-k}\)
This sum is called the Cauchy product or convolution.
4. Solving Combinatorial & Counting Problems
One of the most practical uses of generating functions is counting the number of ways to distribute items or make a total score.
The Big Idea:
• The exponents of \(x\) represent the choices of values (e.g., number of items chosen, or score achieved).
• The coefficients represent the number of ways to make that choice.
• Multiplying brackets corresponds to combining independent choices (the Multiplication Principle).
Worked Example: Making Change
Problem: Find the number of ways to make \(10\text{p}\) using \(1\text{p}\), \(2\text{p}\), and \(5\text{p}\) coins.
Step 1: Write the generating function for each coin type
• For \(1\text{p}\) coins: we can pick \(0, 1, 2, 3, \dots\) coins \(\implies (1 + x + x^2 + x^3 + \dots) = \frac{1}{1-x}\)
• For \(2\text{p}\) coins: the value increases in multiples of \(2\) \(\implies (1 + x^2 + x^4 + x^6 + \dots) = \frac{1}{1-x^2}\)
• For \(5\text{p}\) coins: the value increases in multiples of \(5\) \(\implies (1 + x^5 + x^{10} + \dots) = \frac{1}{1-x^5}\)
Step 2: Form the total generating function
\(G(x) = (1 + x + x^2 + \dots)(1 + x^2 + x^4 + \dots)(1 + x^5 + x^{10} + \dots)\)
Step 3: Extract the coefficient of \(x^{10}\)
We find all combinations of exponents \((a) + (2b) + (5c) = 10\) where \(a, b, c \ge 0\):
• If \(c = 2\) (\(5\text{p} \times 2 = 10\text{p}\)): \(a + 2b = 0 \implies (b=0, a=0)\) (1 way)
• If \(c = 1\) (\(5\text{p} \times 1 = 5\text{p}\)): \(a + 2b = 5 \implies b \in \{0, 1, 2\}\) (3 ways: \(b=0, a=5\); \(b=1, a=3\); \(b=2, a=1\))
• If \(c = 0\) (\(5\text{p} \times 0 = 0\text{p}\)): \(a + 2b = 10 \implies b \in \{0, 1, 2, 3, 4, 5\}\) (6 ways)
Total number of ways \(= 1 + 3 + 6 = 10\) ways.
Key Takeaway
Key Takeaway: When selecting items from different categories, build a polynomial/series for each category and multiply them together. The coefficient of \(x^N\) is the total number of ways to achieve a sum of \(N\).
---5. Solving Recurrence Relations using Generating Functions
Generating functions turn recurrence relations (difference equations) into simple algebra problems!
The 5-Step Master Method
Step 1: Define \(G(x) = \sum_{n=0}^{\infty} u_n x^n\).
Step 2: Multiply the entire recurrence equation by \(x^n\) and sum over all valid \(n\).
Step 3: Express each summation in terms of \(G(x)\) and substitute the given initial conditions.
Step 4: Rearrange the equation to make \(G(x)\) the subject.
Step 5: Split \(G(x)\) using partial fractions and expand using standard series to identify the formula for \(u_n\).
Fully Worked Example: First Order Recurrence
Problem: Solve the recurrence relation \(u_n = 3u_{n-1} + 2\) for \(n \ge 1\), with initial condition \(u_0 = 1\).
Step 1 & 2: Multiply by \(x^n\) and sum for \(n \ge 1\)
\(\sum_{n=1}^{\infty} u_n x^n = 3 \sum_{n=1}^{\infty} u_{n-1} x^n + 2 \sum_{n=1}^{\infty} x^n\)
Step 3: Replace sums with \(G(x)\)
• Left-hand side: \(\sum_{n=1}^{\infty} u_n x^n = G(x) - u_0 = G(x) - 1\)
• Middle term: \(\sum_{n=1}^{\infty} u_{n-1} x^n = x \sum_{n=1}^{\infty} u_{n-1} x^{n-1} = x G(x)\)
• Right-hand side: \(2 \sum_{n=1}^{\infty} x^n = 2 (x + x^2 + x^3 + \dots) = 2 \left(\frac{x}{1-x}\right)\)
Putting it all together:
\(G(x) - 1 = 3x G(x) + \frac{2x}{1 - x}\)
Step 4: Solve for \(G(x)\)
\(G(x) - 3x G(x) = 1 + \frac{2x}{1 - x}\)
\(G(x)(1 - 3x) = \frac{1 - x + 2x}{1 - x} = \frac{1 + x}{1 - x}\)
\(G(x) = \frac{1 + x}{(1 - 3x)(1 - x)}\)
Step 5: Partial fractions and series expansion
Set \(\frac{1 + x}{(1 - 3x)(1 - x)} = \frac{A}{1 - 3x} + \frac{B}{1 - x}\)
\(1 + x = A(1 - x) + B(1 - 3x)\)
• Let \(x = 1\): \(2 = B(1 - 3) = -2B \implies B = -1\)
• Let \(x = \frac{1}{3}\): \(\frac{4}{3} = A\left(\frac{2}{3}\right) \implies A = 2\)
Thus:
\(G(x) = \frac{2}{1 - 3x} - \frac{1}{1 - x}\)
Expanding each term into standard series:
\(G(x) = 2 \sum_{n=0}^{\infty} 3^n x^n - \sum_{n=0}^{\infty} x^n = \sum_{n=0}^{\infty} (2 \cdot 3^n - 1) x^n\)
Equating coefficients of \(x^n\):
\(u_n = 2 \cdot 3^n - 1\)
Quick Check:
• For \(n=0\): \(u_0 = 2 \cdot 3^0 - 1 = 2 - 1 = 1\) (Matches initial condition!)
• For \(n=1\): \(u_1 = 3(1) + 2 = 5\). Formula: \(u_1 = 2 \cdot 3^1 - 1 = 5\) (Correct!)
Second Order Recurrence Relations: Key Conversion Rules
When solving second-order relations \(u_n + a u_{n-1} + b u_{n-2} = f(n)\) for \(n \ge 2\), remember these standard sum conversions:
• \(\sum_{n=2}^{\infty} u_n x^n = G(x) - u_0 - u_1 x\)
• \(\sum_{n=2}^{\infty} u_{n-1} x^n = x \sum_{n=2}^{\infty} u_{n-1} x^{n-1} = x(G(x) - u_0)\)
• \(\sum_{n=2}^{\infty} u_{n-2} x^n = x^2 \sum_{n=2}^{\infty} u_{n-2} x^{n-2} = x^2 G(x)\)
6. Common Mistakes to Avoid
1. Index Offsets: When shifting sums, always check the starting index! For example, \(\sum_{n=1}^{\infty} u_{n-1} x^n = x G(x)\), but \(\sum_{n=2}^{\infty} u_{n-1} x^n = x(G(x) - u_0)\).
2. Negative Binomial Signs: Remember that \(\frac{1}{1 - ax} = 1 + ax + a^2x^2 + \dots\), whereas \(\frac{1}{1 + ax} = 1 - ax + a^2x^2 - \dots\). Watch your minus signs carefully!
3. Forgetting \(u_0\): Always double-check your final general solution by substituting \(n=0\) to see if it matches the given initial value.
---Summary Checklist for Revision
Before heading into the exam, make sure you can:
• State the definition of an ordinary generating function \(G(x) = \sum_{r=0}^{\infty} u_r x^r\).
• Recognize and write down closed forms for standard series like \(\frac{1}{1-ax}\) and \(\frac{1}{(1-x)^n}\).
• Set up product polynomials to solve combinatorial counting/selection problems.
• Use the 5-step method to solve first-order and second-order linear recurrence relations using partial fractions.