Not sure how to do Non-Homogeneous Recurrence Relations

Question

I have a sample exam paper, and the answer is given, but I can't work out the answer from the question:

---

Find the solution of:

$a_n = \frac{1}{3}a_{n-1} + 2$

using $a_0 = 4$

Given Answer: $a_n = 3 + (1/3)^n$

I would like someone to show me how to generally approach these sorts of questions, I can solve Homogeneous Recurrence relations, no problem, but these seem a lot more difficult :/

Answer 1

Here is one approach. Let $a_n=b_n+c$, where $c$ is a constant we will choose later. Then the recurrence becomes $$b_n+c=\frac{1}{3}(b_{n-1}+c)+2.$$ Rewrite as $$b_n=\frac{1}{3}b_{n-1}-\frac{2}{3}c+2.\tag{1}$$ Choose $c$ so that the constant term in (1) is $0$, and solve the homogeneous recurrence $b_n=\frac{1}{3}b_{n-1}$.

Answer 2

$a_n = \frac{1}{3}a_{n-1} + 2$

$a_{n-1} = \frac{1}{3}a_{n-2} + 2$

Subtracting and rearranging gives:

$a_n = \frac{4}{3}a_{n-1}-\frac{1}{3}a_{n-2}$

Putting you back in the homogeneous case.

This method works in some cases when the "let $a_n = b_n +c$" method fails. As a silly example, if we had $a_n = a_{n-1}+1$ then the substitution method would fail but this would still put you back in the homogeneous case.