7.2 Solving recurrence relations using characteristic equations

Solving recurrence relations using characteristic equations is a powerful technique in combinatorics. It transforms complex sequences into manageable polynomial equations, making it easier to find general solutions and analyze long-term behavior.

This method connects various mathematical concepts, from linear algebra to complex analysis. By mastering it, you'll gain valuable tools for tackling a wide range of problems in discrete mathematics and beyond.

Characteristic Equation for Recurrence Relations

Fundamentals of Linear Recurrence Relations

• Linear recurrence relations define each term of a sequence as a linear combination of previous terms
• Characteristic equation transforms the recurrence relation into a polynomial equation
• Set up characteristic equation by replacing each term with $r^n$, where r represents a variable and n denotes the index
• Degree of characteristic equation matches the order of the recurrence relation
• Coefficients in characteristic equation directly correspond to those in the recurrence relation
• Homogeneous linear recurrence relations produce characteristic equations without constant terms
• Non-homogeneous relations include a constant term in the characteristic equation

Transformation Process and Examples

• Setting up characteristic equation shifts problem from sequence domain to polynomial domain
• Example: For recurrence relation $a_n = 3a_{n-1} - 2a_{n-2}$, characteristic equation becomes $r^2 = 3r - 2$
• Higher-order recurrence relation $a_n = 2a_{n-1} + 5a_{n-2} - 6a_{n-3}$ yields characteristic equation $r^3 = 2r^2 + 5r - 6$
• Non-homogeneous example: $a_n = a_{n-1} + a_{n-2} + 3$ transforms to $r^2 = r + 1 + 3$

General Solutions of Recurrence Relations

Root Analysis and Solution Forms

• Roots of characteristic equation determine the form of general solution
• Distinct real roots $r_i$ contribute terms $c_i * (r_i)^n$ to general solution
• Complex conjugate roots yield terms with sine and cosine functions
• Repeated roots of multiplicity m add terms $(polynomial of degree m-1) * r^n$
• Number of terms in general solution equals characteristic equation degree
• Example: For $r^2 - 5r + 6 = 0$ with roots 2 and 3, general solution $a_n = c_1 * 2^n + c_2 * 3^n$

Solving Techniques and Examples

• Solving methods include factoring, quadratic formula, and numerical approaches for higher-degree polynomials
• General solution combines fundamental solutions derived from characteristic equation roots
• Example: Characteristic equation $r^2 - 6r + 9 = 0$ with repeated root 3 gives solution $a_n = (c_1 + c_2n) * 3^n$
• Complex roots case: $r^2 + 4r + 5 = 0$ with roots $-2 + i$ and $-2 - i$ yields solution $a_n = c_1 * (-1)^n * e^{-2n} * cos(n) + c_2 * (-1)^n * e^{-2n} * sin(n)$

Particular Solutions from Initial Conditions

Applying Initial Conditions

• Particular solution obtained by using given initial conditions with general solution
• Number of required initial conditions equals recurrence relation order
• Initial conditions create system of linear equations when substituted into general solution
• Solving equation system determines constants in general solution
• Non-homogeneous recurrence relations require both homogeneous and non-homogeneous solution parts
• Method of undetermined coefficients finds form of non-homogeneous solution part
• Verify particular solution satisfies both recurrence relation and initial conditions

Solution Process and Examples

• Example: For $a_n = 3a_{n-1} - 2a_{n-2}$ with $a_0 = 1$ and $a_1 = 2$, solve system: $1 = c_1 + c_2$ $2 = c_1 * 2 + c_2 * 1$
• Solution yields $c_1 = 1$ and $c_2 = 0$, giving particular solution $a_n = 2^n$
• Non-homogeneous example: $a_n = 2a_{n-1} + 3$ with $a_0 = 1$ Homogeneous solution: $a_n = c * 2^n$ Particular solution: $a_n = -3$ Combine: $a_n = c * 2^n - 3$ Apply initial condition: $1 = c - 3$, so $c = 4$ Final solution: $a_n = 4 * 2^n - 3$

Sequence Behavior vs Characteristic Roots

Long-term Behavior Analysis

• Dominant root (largest absolute value) determines long-term sequence behavior
• Real positive dominant root > 1 causes exponential growth, < 1 leads to decay
• Negative dominant root creates alternating sequence, may grow or decay in magnitude
• Complex roots produce oscillatory behavior in sequence
• Multiple roots of same magnitude can result in polynomial growth factors
• Apply ratio test to confirm growth or decay rate predicted by characteristic roots
• Example: Sequence with characteristic roots 2 and -1 grows exponentially due to dominant root 2

Stability Analysis and Examples

• Examine magnitude of all characteristic roots relative to unit circle for stability analysis
• Roots inside unit circle lead to convergent sequence
• Roots outside unit circle result in divergent sequence
• Roots on unit circle may produce bounded oscillations
• Example: Recurrence $a_n = 1.5a_{n-1} - 0.5a_{n-2}$ with roots 1 and 0.5 grows linearly due to root on unit circle
• Complex roots example: $a_n = 2a_{n-1} - 2a_{n-2}$ with roots $1 + i$ and $1 - i$ produces growing oscillations