Chapter 6: Method of Characteristic Roots for Solving Recurrence Relations
Solving Homogeneous, Inhomogeneous & Nonlinear Recurrence Relations
(TB1 Ch.3, Articles 5–6)
1. Recurrence Relations Revisited
A recurrence relation defines a sequence in terms of its previous terms.
General Form
[ a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} + f(n) ]
- If ( f(n) = 0 ) → Homogeneous
- If ( f(n) \neq 0 ) → Inhomogeneous
2. Method of Characteristic Roots
(For Linear Homogeneous Recurrence Relations with Constant Coefficients)
Standard Form
[ a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} ]
Basic Idea
Assume a solution of the form: [ a_n = r^n ]
Substitute into the recurrence relation to obtain the characteristic equation.
3. Solving Second-Order Homogeneous Recurrence Relations
General Form
[ a_n = c_1 a_{n-1} + c_2 a_{n-2} ]
Characteristic Equation
[ r^2 - c_1 r - c_2 = 0 ]
4. Cases Based on Roots
Case 1: Distinct Real Roots
If roots are ( r_1 \neq r_2 ):
[ a_n = A r_1^n + B r_2^n ]
Constants (A, B) are determined using initial conditions.
Example 1
[ a_n = 5a_{n-1} - 6a_{n-2}, \quad a_0 = 1,; a_1 = 4 ]
Characteristic equation [ r^2 - 5r + 6 = 0 ]
Roots: ( r = 2, 3 )
[ a_n = A(2^n) + B(3^n) ]
Using initial conditions: [ A + B = 1 ] [ 2A + 3B = 4 ]
Solving: [ A = -1,; B = 2 ]
[ \boxed{a_n = -2^n + 2 \cdot 3^n} ]
Case 2: Repeated Roots
If root ( r ) has multiplicity 2:
[ a_n = (A + Bn)r^n ]
Example 2
[ a_n = 2a_{n-1} - a_{n-2}, \quad a_0 = 1,; a_1 = 2 ]
Characteristic equation: [ (r - 1)^2 = 0 ]
[ a_n = (A + Bn)1^n = A + Bn ]
Using conditions: [ A = 1,; B = 1 ]
[ \boxed{a_n = 1 + n} ]
Case 3: Complex Roots
If roots are ( \alpha \pm i\beta ):
[ a_n = r^n (A\cos n\theta + B\sin n\theta) ]
(where ( r = \sqrt{\alpha^2 + \beta^2} ))
5. Inhomogeneous Recurrence Relations
General Form
[ a_n = c_1 a_{n-1} + c_2 a_{n-2} + f(n) ]
Solution Structure
[ \boxed{a_n = a_n^{(h)} + a_n^{(p)}} ]
Where:
- ( a_n^{(h)} ): Solution of homogeneous part
- ( a_n^{(p)} ): Particular solution
6. Finding Particular Solutions
Common Forms of ( f(n) )
| (f(n)) | Guess for (a_n^{(p)}) |
|---|---|
| Constant | Constant |
| Polynomial | Polynomial |
| (c^n) | (A c^n) |
| (n c^n) | ((An+B)c^n) |
Example 3
[ a_n = 2a_{n-1} + 3, \quad a_0 = 1 ]
Homogeneous solution: [ a_n^{(h)} = A2^n ]
Try constant particular solution (a_n^{(p)} = C):
[ C = 2C + 3 \Rightarrow C = -3 ]
[ a_n = A2^n - 3 ]
Using (a_0 = 1): [ A - 3 = 1 \Rightarrow A = 4 ]
[ \boxed{a_n = 4\cdot2^n - 3} ]
7. When ( f(n) ) Matches Homogeneous Solution
Multiply the guessed solution by (n).
Example 4
[ a_n = a_{n-1} + 2^n ]
Since (2^n) is already part of homogeneous solution, try: [ a_n^{(p)} = n2^n ]
8. Nonlinear Recurrence Relations
Definition
A recurrence relation is nonlinear if it contains products or powers of terms.
[ a_n = a_{n-1}^2,\quad a_n = a_{n-1} a_{n-2} ]
Example 5
[ a_n = a_{n-1}^2,\quad a_0 = 2 ]
[ a_1 = 4,; a_2 = 16,; a_3 = 256 ]
Closed form: [ \boxed{a_n = 2^{2^n}} ]
Note
- Nonlinear recurrences usually do not have general closed-form solutions.
-
Solved using:
-
Pattern observation
- Substitution
- Iteration
9. Comparison: Generating Functions vs Characteristic Roots
| Aspect | Generating Functions | Characteristic Roots |
|---|---|---|
| Best for | Inhomogeneous, counting | Linear homogeneous |
| Complexity | Higher | Lower |
| Initial conditions | Built-in | Separate step |