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

Non-Homogeneous Recurrence Relations

Introduce non-homogeneous recurrences with a non-zero right-hand side term f(n).

Non-Homogeneous Recurrence Relations

What you'll learn: You'll discover how recurrence relations change when they include an extra "forcing" term that depends on n.

The Core Idea

Until now, you've worked with homogeneous recurrence relations where each term depends only on previous terms—like a_n = 3a_{n-1} - 2a_{n-2}. But many real-world problems produce relations with an additional term on the right side that isn't just a multiple of previous terms.

A non-homogeneous recurrence relation has the form:

a_n = (combination of previous terms) + f(n)

where f(n) is a function of n alone, not involving a_{n-1}, a_{n-2}, etc. This f(n) is called the non-homogeneous term or forcing function.

Examples

  • a_n = 2a_{n-1} + 3: Here f(n) = 3 (a constant)
  • a_n = a_{n-1} + a_{n-2} + n: Here f(n) = n (linear in n)
  • a_n = 3a_{n-1} - n²: Here f(n) = -n²

The homogeneous part (the terms involving previous a's) follows the same rules you've learned. The challenge is handling that extra f(n) term.

Think of It This Way

Imagine a savings account where you earn interest based on your balance (the homogeneous part), but you also deposit a fixed amount each month (the non-homogeneous term). The recurrence isn't purely self-referential anymore—there's an external input pushing the sequence in a particular direction.

Key Takeaway: Non-homogeneous recurrence relations add a non-zero term f(n) to the standard homogeneous structure, representing external inputs or forcing functions that affect the sequence independently of its previous values.