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.