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

General Solution of Non-Homogeneous Recurrences

Combine homogeneous and particular solutions to form the complete general solution of non-homogeneous recurrences.

General Solution of Non-Homogeneous Recurrences

What You'll Learn

You'll learn how to combine the homogeneous and particular solutions to write the complete general solution for non-homogeneous recurrence relations.

The Complete Picture

When solving a non-homogeneous recurrence relation, you're dealing with an equation that has an extra "forcing term" on the right side—something that doesn't depend on previous terms alone. Think of it like describing motion with both natural momentum (homogeneous part) and an external push (particular part).

The beauty of linear non-homogeneous recurrences is that the general solution is always the sum of two components:

  1. Homogeneous solution (a_n^(h)): The solution to the associated homogeneous recurrence (when you set the non-homogeneous term to zero)
  2. Particular solution (a_n^(p)): Any specific solution that satisfies the full non-homogeneous equation

The Formula

For a non-homogeneous recurrence, the general solution is:

a_n = a_n^(h) + a_n^(p)

Why This Works

This works because of the linearity of the recurrence. If you substitute this combined solution back into the original recurrence relation, the homogeneous part handles the left-hand dependencies (the terms involving previous values), while the particular solution handles the forcing term.

The homogeneous solution contains arbitrary constants that you'll determine using initial conditions. The particular solution is fixed (no free constants).

Example Pattern

If your homogeneous solution is a_n^(h) = c₁ · 2^n + c₂ · 3^n and you found a particular solution a_n^(p) = 5n + 2, then:

General solution: a_n = c₁ · 2^n + c₂ · 3^n + 5n + 2

Use initial conditions to solve for c₁ and c₂.

Key Takeaway: The general solution of a non-homogeneous recurrence is the sum of its homogeneous solution and any particular solution: a_n = a_n^(h) + a_n^(p).