1. **State the problem:** Solve the recurrence relation $$a_n - 5a_{n-1} + 6a_{n-2} = 2^n, \quad n \geq 2$$ with initial conditions $$a_0 = 1, \quad a_1 = 1$$ using generating functions. 2. **Define the generating function:** Let $$A(x) = \sum_{n=0}^\infty a_n x^n$$ be the generating function for the sequence $a_n$. 3. **Write the recurrence in terms of generating functions:** Multiply both sides of the recurrence by $x^n$ and sum over $n \geq 2$: $$\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 = \sum_{n=2}^\infty 2^n x^n$$ 4. **Express sums in terms of $A(x)$:** - $$\sum_{n=2}^\infty a_n x^n = A(x) - a_0 - a_1 x = A(x) - 1 - x$$ - $$\sum_{n=2}^\infty a_{n-1} x^n = x \sum_{n=1}^\infty a_n x^{n} = x (A(x) - a_0) = x (A(x) - 1)$$ - $$\sum_{n=2}^\infty a_{n-2} x^n = x^2 \sum_{n=0}^\infty a_n x^n = x^2 A(x)$$ - $$\sum_{n=2}^\infty 2^n x^n = \sum_{n=2}^\infty (2x)^n = \frac{(2x)^2}{1 - 2x} = \frac{4x^2}{1 - 2x}$$ 5. **Substitute back into the equation:** $$A(x) - 1 - x - 5x (A(x) - 1) + 6x^2 A(x) = \frac{4x^2}{1 - 2x}$$ 6. **Simplify the left side:** $$A(x) - 1 - x - 5x A(x) + 5x + 6x^2 A(x) = \frac{4x^2}{1 - 2x}$$ Group terms: $$A(x)(1 - 5x + 6x^2) + (-1 - x + 5x) = \frac{4x^2}{1 - 2x}$$ $$A(x)(1 - 5x + 6x^2) + (-1 + 4x) = \frac{4x^2}{1 - 2x}$$ 7. **Isolate $A(x)$:** $$A(x)(1 - 5x + 6x^2) = \frac{4x^2}{1 - 2x} + 1 - 4x$$ 8. **Factor the quadratic:** $$1 - 5x + 6x^2 = (1 - 2x)(1 - 3x)$$ 9. **Rewrite $A(x)$:** $$A(x) = \frac{\frac{4x^2}{1 - 2x} + 1 - 4x}{(1 - 2x)(1 - 3x)} = \frac{4x^2 + (1 - 4x)(1 - 2x)}{(1 - 2x)^2 (1 - 3x)}$$ 10. **Expand numerator:** $$(1 - 4x)(1 - 2x) = 1 - 2x - 4x + 8x^2 = 1 - 6x + 8x^2$$ So numerator: $$4x^2 + 1 - 6x + 8x^2 = 1 - 6x + 12x^2$$ 11. **Final form:** $$A(x) = \frac{1 - 6x + 12x^2}{(1 - 2x)^2 (1 - 3x)}$$ 12. **Partial fraction decomposition:** Write $$\frac{1 - 6x + 12x^2}{(1 - 2x)^2 (1 - 3x)} = \frac{A}{1 - 3x} + \frac{B}{1 - 2x} + \frac{C}{(1 - 2x)^2}$$ Multiply both sides by denominator: $$1 - 6x + 12x^2 = A(1 - 2x)^2 + B(1 - 2x)(1 - 3x) + C(1 - 3x)$$ Expand: - $(1 - 2x)^2 = 1 - 4x + 4x^2$ - $(1 - 2x)(1 - 3x) = 1 - 5x + 6x^2$ So: $$1 - 6x + 12x^2 = A(1 - 4x + 4x^2) + B(1 - 5x + 6x^2) + C(1 - 3x)$$ Group terms: $$1 - 6x + 12x^2 = (A + B + C) + (-4A - 5B - 3C)x + (4A + 6B) x^2$$ Match coefficients: - Constant: $1 = A + B + C$ - $x$: $-6 = -4A - 5B - 3C$ - $x^2$: $12 = 4A + 6B$ 13. **Solve system:** From $x^2$: $$12 = 4A + 6B \implies 2 = \frac{4A}{6} + B = \frac{2A}{3} + B$$ Or better: $$4A + 6B = 12$$ From constant: $$C = 1 - A - B$$ Substitute $C$ into $x$ coefficient: $$-6 = -4A - 5B - 3(1 - A - B) = -4A - 5B - 3 + 3A + 3B = (-4A + 3A) + (-5B + 3B) - 3 = -A - 2B - 3$$ So: $$-6 + 3 = -A - 2B \implies -3 = -A - 2B \implies A + 2B = 3$$ Now system: $$4A + 6B = 12$$ $$A + 2B = 3$$ Multiply second by 4: $$4A + 8B = 12$$ Subtract first from this: $$(4A + 8B) - (4A + 6B) = 12 - 12 \implies 2B = 0 \implies B = 0$$ Then from $A + 2B = 3$: $$A + 0 = 3 \implies A = 3$$ From $C = 1 - A - B$: $$C = 1 - 3 - 0 = -2$$ 14. **Rewrite generating function:** $$A(x) = \frac{3}{1 - 3x} + \frac{0}{1 - 2x} + \frac{-2}{(1 - 2x)^2} = \frac{3}{1 - 3x} - \frac{2}{(1 - 2x)^2}$$ 15. **Find $a_n$ from generating function:** Recall: - $$\frac{1}{1 - rx} = \sum_{n=0}^\infty r^n x^n \implies a_n = r^n$$ - $$\frac{1}{(1 - rx)^2} = \sum_{n=0}^\infty (n+1) r^n x^n$$ So: $$a_n = 3 \cdot 3^n - 2 (n+1) 2^n = 3^{n+1} - 2 (n+1) 2^n$$ 16. **Check initial conditions:** - For $n=0$: $$a_0 = 3^{1} - 2 (1) 2^{0} = 3 - 2 = 1$$ - For $n=1$: $$a_1 = 3^{2} - 2 (2) 2^{1} = 9 - 8 = 1$$ Matches initial conditions. **Final answer:** $$\boxed{a_n = 3^{n+1} - 2 (n+1) 2^n}$$