Chapter 5: Recurrence Relations & Solving Recurrence Relations with Generating Functions
(TB1 Ch.3, Articles 3–4)
1. Recurrence Relations
Definition
A recurrence relation is an equation that defines a sequence in terms of previous terms of the sequence.
[ a_n = f(a_{n-1}, a_{n-2}, \dots, a_{n-k}) ]
To determine a unique solution, initial conditions are required.
Examples
-
Arithmetic progression: [ a_n = a_{n-1} + d ]
-
Fibonacci sequence: [ F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0, F_1 = 1 ]
2. Types of Recurrence Relations
(a) Linear vs Nonlinear
- Linear: Terms appear to power 1 [ a_n = 3a_{n-1} - 2a_{n-2} ]
- Nonlinear: Products or powers [ a_n = a_{n-1}^2 ]
(b) Homogeneous vs Inhomogeneous
- Homogeneous: No independent term [ a_n = a_{n-1} + a_{n-2} ]
- Inhomogeneous: Contains external term [ a_n = a_{n-1} + n ]
3. Solving Recurrence Relations Using Generating Functions
Generating functions transform recurrence relations into algebraic equations, which are easier to solve.
4. Method of Generating Functions
Let: [ G(x) = \sum_{n=0}^{\infty} a_n x^n ]
General Steps
- Write the recurrence relation.
- Multiply both sides by (x^n).
- Sum over all relevant values of (n).
- Use initial conditions to simplify.
- Solve for (G(x)).
- Extract coefficient (a_n).
5. Example 1: First-Order Linear Recurrence
Problem
Solve: [ a_n = a_{n-1}, \quad a_0 = 1 ]
Solution
Multiply both sides by (x^n) and sum for (n \ge 1):
[ \sum_{n=1}^{\infty} a_n x^n = \sum_{n=1}^{\infty} a_{n-1} x^n ]
Left side: [ G(x) - a_0 ]
Right side: [ xG(x) ]
So: [ G(x) - 1 = xG(x) ]
[ G(x) = \frac{1}{1-x} ]
Hence: [ a_n = 1 ]
6. Example 2: Fibonacci Sequence
[ F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0, F_1 = 1 ]
Solution
Define: [ F(x) = \sum_{n=0}^{\infty} F_n x^n ]
Multiply recurrence by (x^n) and sum for (n \ge 2):
[ \sum_{n=2}^{\infty} F_n x^n ===========================
\sum_{n=2}^{\infty} F_{n-1} x^n + \sum_{n=2}^{\infty} F_{n-2} x^n ]
Simplify: [ F(x) - x = xF(x) + x^2F(x) ]
[ F(x)(1 - x - x^2) = x ]
[ F(x) = \frac{x}{1 - x - x^2} ]
Coefficient Extraction
Using partial fractions or known expansion, we obtain Fibonacci numbers.
7. Example 3: Inhomogeneous Recurrence
Problem
[ a_n = a_{n-1} + 1, \quad a_0 = 0 ]
Solution
Generating function: [ G(x) = \sum a_n x^n ]
[ G(x) = xG(x) + \frac{1}{1-x} ]
[ G(x) = \frac{1}{(1-x)^2} ]
Thus: [ a_n = n ]
8. Higher-Order Recurrence Relations
Example
[ a_n = 2a_{n-1} + a_{n-2}, \quad a_0 = 1, a_1 = 2 ]
Generating function leads to: [ G(x) = \frac{1 + x}{1 - 2x - x^2} ]
9. Why Use Generating Functions?
- Handles initial conditions naturally
- Works for inhomogeneous recurrences
- Produces closed-form solutions
- Useful in algorithm analysis