Nonhomogeneous Recurrences

Combinatorics · Axiom Academy

LESSON Nonhomogeneous Recurrences Learn how to solve nonhomogeneous recurrence relations by combining particular and homogeneous solutions 1. Understanding Nonhomogeneous Recurrences A nonhomogeneous recurrence has the form: The solution consists of two parts: a_n^ (h) is the general solution to the associated homogeneous recurrence a_n^ (p) is a particular solution to the nonhomogeneous recurrence 2. Finding the Homogeneous Solution First, solve the associated homogeneous recurrence by setting f(n) = 0: 3. Finding a Particular Solution The form of the particular solution depends on f(n). Common cases: If f(n) is constant c, try a_n^ (p) = p (constant) If f(n) = d · n, try a_n^ (p) = pn + q (linear) If f(n) = d · n^2, try a_n^ (p) = pn^2 + qn + r (quadratic) If f(n) = d · s^n, try a_n^ (p) = p · s^n (unless s is a characteristic root) Add the homogeneous and particular solutions: 5. Special Case: When f(n) Matches a Characteristic Root If f(n) = d · r^n where r is a characteristic root of multiplicity m, multiply the trial solution by n^m:

This is the written version of the interactive lesson above. See the full Combinatorics course.