Course contentsShow
← Mathematics
Lesson 2634 of 3,12152. CombinatoricsFree lesson

Finding Particular Solutions

Learn methods to find particular solutions for common forms of f(n) like constants, polynomials, and exponentials.

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.