How to solve a 2nd order non-homogeneous linear recurrence? I have a problem in solving this equation :
$x_{n+2} + 3\ x_{n+1} + 2\ x_{n} = 5 \times 3^n $
given that $x_{0} = 0$ and $x_{1} = 1$.
I solved the homogeneous associated equation and got $v_{n} = c_{1} \times (-1)^{n} + c_{2} \times (-2)^{n}$ (where $c_{1}$ and $c_{2}$ are constants). 
Could somebody explain the general method for solving second order non-homogeneous linear recurrence ?
 A: Well, you need to find a particular solution of the inhomogeneous equation, and the rhs suggest that something of the form $c(n)3^n$ should work. The simplest form of $c$ is a constant, so try that. If it works, you are golden, if not, try a linear function, etc, then add the homogeneous solution and you are good.
A: I have just found the solution. This is not general method, but some piece of heuristics. May be it somehow will help you to find some solutions in simple cases.
I use method of undetermined coeficients. I guess, that should be $$x_n=c3^n+d(-1)^n,$$ for some real constants $c,d$. Now, calculation of $c,d$ is very simple. We have also 
$$x_{n+1}=3c3^n-d(-1)^n$$
$$x_{n+2}=9c3^n+d(-1)^n,$$
so:
$$x_{n+2}+3x_{n+1}+2x_n=9c3^n+d(-1)^n+ 9c3^n-3d(-1)^n+2c3^n+2d(-1)^n=20c3^{n}$$
From the recurrence must be: $$20c3^{n}=5.3^n,$$ so: $c=\frac{1}{4}$.
Now we know, that $$\frac{3^n}{4}+d(-1)^n$$ satisfies your recurrence. And because $x_0=0$, we must have $d=-\frac14$.
Therefore we have following result:
$$x_n=\frac{3^n}{4}-\frac{(-1)^n}4.$$
A: Use generating functions directly. Define $G(z) = \sum_{n \ge 0} x_n z^n$, multiply by $z^n$ and sum over $n \ge 0$, recognize a few sums:
$$
\frac{G(z) - x_0 - x_1 z}{z^2} + 3 \frac{G(z) - x_0}{z} + 2 G(z)
  = 5 \frac{1}{1 - 3 z}
$$
As partial fractions:
$$
A(z) = \frac{1}{4} \cdot \frac{1}{1 - 3 z} - \frac{1}{4} \cdot \frac{1}{1 + z}
$$
Everything in sight is just geometric series;
$$
a_n
  = \frac{3^n - (-1)^n}{4}
$$
