How to solve recurrence relations using the characteristic equation method?

**General Method for Linear Recurrences:** A linear homogeneous recurrence $a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}$ has characteristic equation: $$r^k - c_1 r^{k-1} - \cdots - c_k = 0$$ **Case 1: Distinct Real Roots** If roots are $r_1, r_2, \ldots, r_k$, then: $$a_n = \alpha_1 r_1^n + \alpha_2 r_2^n + \cdots + \alpha_k r_k^n$$ Your example: $a_n = 5a_{n-1} - 6a_{n-2}$, $a_0 = 1$, $a_1 = 2$. $r^2 - 5r + 6 = 0 \Rightarrow r = 2, 3$. $a_n = \alpha(2^n) + \beta(3^n)$. $a_0 = \alpha + \beta = 1$, $a_1 = 2\alpha + 3\beta = 2$. Solving: $\alpha = 1$, $\beta = 0$. So $a_n = 2^n$. **Case 2: Repeated Roots** If root $r$ has multiplicity $m$, the terms are $\alpha_1 r^n + \alpha_2 n r^n + \alpha_3 n^2 r^n + \cdots + \alpha_m n^{m-1} r^n$. For $a_n = 4a_{n-1} - 4a_{n-2}$: $r^2 - 4r + 4 = 0 \Rightarrow r = 2$ (multiplicity 2). $a_n = (\alpha + \beta n)2^n$. **Case 3: Non-Homogeneous Recurrences** For $a_n = 3a_{n-1} + 2^n$: - Solve homogeneous part: $a_n^{(h)} = \alpha \cdot 3^n$ - Find particular solution: since RHS is $2^n$, try $a_n^{(p)} = C \cdot 2^n$: $$C \cdot 2^n = 3C \cdot 2^{n-1} + 2^n \Rightarrow 2C = 3C + 2 \Rightarrow C = -2$$ - General: $a_n = \alpha \cdot 3^n - 2 \cdot 2^n = \alpha \cdot 3^n - 2^{n+1}$ - Use initial conditions to find $\alpha$. **Case 4: Complex Roots** If $r = re^{\pm i\theta}$, then $a_n = r^n(\alpha \cos(n\theta) + \beta \sin(n\theta))$.