Non-Homogeneous Recurrences

Discrete Math · Axiom Academy

LESSON Non-Homogeneous Recurrences Master the method of undetermined coefficients to find particular solutions for polynomial, exponential, and trigonometric forcing functions. The general solution is the sum of two parts: 2. Polynomial Forcing Functions When f(n) is a polynomial of degree d, our guess for the particular solution should also be a polynomial of degree d. 3. Exponential Forcing Functions When f(n) is exponential (like cⁿ), our particular solution takes a similar exponential form—but watch out for a special case! Follow these systematic steps to solve any non-homogeneous recurrence: Find homogeneous solution: Solve the characteristic equation for aₙ⁽ʰ⁾ Identify f(n) type: Polynomial, exponential, or combination Make educated guess: Choose form for aₙ⁽ᵖ⁾ based on f(n) Substitute and solve: Plug guess into recurrence, solve for coefficients Combine solutions: aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾ Apply initial conditions: Find specific constants

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