I have been looking around for a general method to solve non-homogeneous recurrence relations.
Establishing formula from recurrence. Brian's answer explains that his method is better suited for relations of the form $f(n)=af(n−1)$. What if my relation is not of that form?
Can you explain to me how to solve non-homogeneous recurrence relations?
For instance, this
$$f(1) = f(2) = K$$
$$f(n) = f(n-1) + 2f(n-2) + n + 2^n + K$$
I only know part of the process:
First, we take care of the homogeneous part:
$$f(n) - f(n-1) - 2f(n-2)$$
The characteristic equation is:
Which factors to:
$$(a - 2)(a + 1)$$
Therefore, the homogeneous formula is of the form:
$$f_H(n) = b_1(2)^n+b_2(-1)^n$$
And this is as much as I know about non-homogeneous recurrence relations. How do I proceed? I've seen several documents, but somehow, they all seem to describe different concepts that just end up confusing me more.