How to solve non-homogeneous recurrence relations? I have been looking around for a general method to solve non-homogeneous recurrence relations.


*

*Solving non homogeneous recurrence relation seems to be having almost the same problem as me. There is one answer that I absolutely don't understand.

*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:
$$a^2-a-2$$
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.
 A: Just use generating functions. Define $F(z) = \sum_{n \ge 0} f(n + 1) z^n$, write your recurrence as:
$$
f(n + 2) = f(n + 1) + 2 f(n) + n + 2 + 4 \cdot 2^n + K
$$
Multiply by $z^n$, sum over $n \ge 0$, recognize the resulting sums:
$$
\frac{F(z) - f(1) - f(2) z}{z^2}
  = \frac{F(z) - f(1)}{z} + 2 F(z)
      + \frac{z}{(1 - z)^2}
      + \frac{4}{1 - 2 z}
      + \frac{K + 2}{1 - z}
$$
This because:
\begin{align}
\sum_{n \ge 0} z^n
  &= \frac{1}{1 - z} \\
\sum_{n \ge 0} n z^n
  &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\
  &= \frac{z}{(1 - z)^2}
\end{align}
Solving for $F(z)$, as partial fractions:
$$
F(z) 
   = \frac{6 K + 13}{12(1 + z)}
        + \frac{3 K - 1}{1 - 2 z}
        - \frac{2 K + 5}{4 (1 - z)}
        + \frac{2}{3 (1 - 2 z)^2}
        - \frac{1}{6 (1 + z)^2}
$$
Using the generalized binomial theorem you have:
$$
\binom{-m}{k} = (-1)^k \binom{m + k - 1}{m - 1}
$$
In particular:
$$
\binom{-2}{k} = (-1)^k (k + 1)
$$
This allows to read off the coefficients from the above.
A: Try  putting $an+b+cn2^{n}$ into the equation where $a,b,c$ are some constants to be determined and see if the recurrence holds.
A: I will use lance wellton's method and finish the problem. It is based on the very simple undetermined method for linear non-homogeneous differential equations, which you can find in any elementary ODE book. As lance wellton suggests, just try $f(n)=an+b+cn2^n$. Then $$f(n)-f(n−1)-2f(n−2)=-2an+(5a-2b)+3c\,2^n/2.\qquad (1)$$
We want the RHS of (1) to be equal to $n+2^n+K$, hence we set $c=2/3$, $a=-1/2$, $b=-K/2-5/4$ and the general solution reads:
$$
f(n)= b_1\,2^n+b_2\,(−1)^n-n/2-K/2-5/2+2n2^n/3.
$$
Then use $b_1$ and $b_2$ to get you boundary conditions.
