How to solve recurrence relations using generating functions?

Using **Generating Functions** transforms a discrete sequence relation into a continuous algebraic equation. Once solved, you expand that function back into a power series to extract the explicit formula. **Step-by-Step Solution for $a_n = 5a_{n-1} - 6a_{n-2}$** Given the relation: $$a_n = 5a_{n-1} - 6a_{n-2} \quad (n \ge 2) \quad \text{with } a_0 = 1, a_1 = 2$$ We define our generating function as: $$G(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \dots$$ **1. Multiply and Sum** Multiply the entire recurrence relation by $x^n$ and sum from $n = 2$ to $\infty$: $$\sum_{n=2}^{\infty} a_n x^n = 5 \sum_{n=2}^{\infty} a_{n-1} x^n - 6 \sum_{n=2}^{\infty} a_{n-2} x^n$$ **2. Substitute $G(x)$ Templates** We rewrite each summation piece by shifting indices to match our base $G(x)$ function: - **Left Side:** Missing the first two terms ($a_0 + a_1 x$). $$\sum_{n=2}^{\infty} a_n x^n = G(x) - 1 - 2x$$ - **First Right Term:** Factor out $x$ to align the index. Missing the $a_0$ term. $$5x \sum_{n=2}^{\infty} a_{n-1} x^{n-1} = 5x(G(x) - 1) = 5xG(x) - 5x$$ - **Second Right Term:** Factor out $x^2$ to align the index. Represents a clean $G(x)$. $$-6x^2 \sum_{n=2}^{\infty} a_{n-2} x^{n-2} = -6x^2 G(x)$$ **3. Solve for $G(x)$** Plug these components back into the main equation: $$(G(x) - 1 - 2x) = 5xG(x) - 5x - 6x^2 G(x)$$ Group all $G(x)$ terms onto the left side: $$G(x)(1 - 5x + 6x^2) = 1 - 3x$$ Isolate your generating function: $$G(x) = \frac{1 - 3x}{1 - 5x + 6x^2}$$ **4. Simplify and Extract $a_n$** Factor the denominator to simplify the fraction: $1 - 5x + 6x^2 = (1 - 2x)(1 - 3x)$. $$G(x) = \frac{1 - 3x}{(1 - 2x)(1 - 3x)} = \frac{1}{1 - 2x}$$ Apply the standard geometric series expansion $\frac{1}{1-u} = \sum_{n=0}^{\infty} u^n$ where $u = 2x$: $$G(x) = \sum_{n=0}^{\infty} (2x)^n = \sum_{n=0}^{\infty} \mathbf{2^n} x^n$$ By matching the coefficients with $G(x) = \sum_{n=0}^{\infty} a_n x^n$, we get the final explicit formula: $$a_n = 2^n$$