solution of a recurrence How might one solve the recurrence 
$x_{n+1} + x_n + 2^n = 0$
given the necessary initial conditions ($x_0$)? 
Possible ideas I have in mind:
1) 
Generating functions
2) Discrete Laplace Transforms
Any other possible techniques?
 A: Divide by $2^{n}$, we then get
$$\dfrac{x_{n+1}}{2^n} + \dfrac{x_n}{2^n} + 1 = 0$$
Let $y_n = \dfrac{x_n}{2^n}$. This gives us $$2y_{n+1} + y_n + 1 = 0 \implies 2(y_{n+1}+1/3) + (y_n+1/3) = 0$$
Define $z_n = y_n + 1/3$ to get
$$2z_{n+1} = -z_n \implies z_{n+1} = \left(-\dfrac12\right)^{n+1} z_0$$
Obtain $x_n$ from this.
Move your mouse over the gray area for the complete solution.

$$y_n = -\dfrac13 + \left(-\dfrac12\right)^{n}(y_0+1/3) \implies x_n = -\dfrac{2^n}3 + (-1)^n\left(\dfrac{x_0}{2^n}+\dfrac13\right)$$$$x_n = \left(-\dfrac12\right)^nx_0 + \dfrac{(-1)^n-2^n}3$$

A: Generating functions: Define $X(z) = \sum_{n \ge 0} x_n z^n$, multiply by $z^n$ and sum over $n \ge 0$ to get:
$$
\frac{X(z) - x_0}{z} + X(z) + \frac{1}{1 - 2 z} = 0
$$
Thus, written as partial fractions:
$$
X(z) = \frac{1 + 3 x_0}{3 (1 + z)} - \frac{1}{3 (1 - 2 z)}
$$
From here the coefficients can be read off directly:
$$
x_n = \frac{1 + 3 x_0}{3} \cdot (-1)^n - \frac{2^n}{3}
$$
A: The general solution of the homogeneous equation $x_{n+1}=-x_n$ is $A(-1)^n$. Now look for a particular solution of the inhomogeneous equation. "Guess" that there is a solution of the shape $k2^n$. We get $k2^{n+1}+k2^n=-2^n$, giving $k=-\frac{1}{3}$. thus the general solution is $-\frac{2^n}{3}+(-1)^n A$. 
