Finding Particular Solutions
You'll learn: How to find a particular solution to match the non-homogeneous part of a recurrence relation for common forms like constants, polynomials, and exponentials.
Why We Need Particular Solutions
When solving non-homogeneous recurrence relations (ones with an added function f(n)), the general solution is the sum of two parts: the homogeneous solution and a particular solution. The particular solution is a specific sequence that satisfies the full non-homogeneous equation—it accounts for the "extra" f(n) term.
The Method: Guess and Check
The key is to guess the form of the particular solution based on f(n), then substitute it into the recurrence to find the coefficients.
For Constants: f(n) = c
Guess a constant particular solution: p(n) = A Substitute and solve for A.
Example: If a_n = 2a_{n-1} + 3, guess p(n) = A, substitute to get A = 2A + 3, so A = -3.
For Polynomials: f(n) = polynomial of degree d
Guess a polynomial of the same degree: p(n) = A_d·n^d + A_{d-1}·n^{d-1} + ... + A_0 Substitute and match coefficients on both sides.
Example: If f(n) = 2n + 1, guess p(n) = An + B.
For Exponentials: f(n) = c·r^n
Guess an exponential of the same base: p(n) = A·r^n Substitute and solve for A.
Example: If f(n) = 5·3^n, guess p(n) = A·3^n.
Special Case: Form Matches Homogeneous Solution
If your guess matches a solution to the homogeneous equation (a root collision), multiply by n until you get something new.
Key Takeaway: Match the form of f(n) with your particular solution guess—constant for constant, polynomial for polynomial, exponential for exponential—then solve for unknown coefficients by substitution.