Solving recursion with generating function I am trying to solve a recursion with generating function, but somehow I ended up with mess.....
$$y_n=y_{n-1}-2y_{n-2}+4^{n-2}, y_0=2,y_1=1 $$
\begin{eqnarray*}
g(x)&=&y_0+y_1x+\sum_2^{\infty}(y_{n-1}-2y_{n-2}+4^{n-2})x^n\\
&=&2+x+\sum^{\infty}_2y_{n-1}x^n-2\sum_2^{\infty}y_{n-2}x^n+\sum_2^{\infty}4^{n-2}x^n\\
&=&2+x+x\sum_1^{\infty}y_{n-1}x^{n-1}-2x^2\sum_0^{\infty}y_{n-2}x^{n-2}+\frac{1}{4^2}\sum^{\infty}_{2}(4x)^{n}\\
&=&2+x+x(g(x)-1)-2x^2g(x)+\frac{1}{4^2}\left(\frac{1}{1-4x}-1-4x\right)\\
g(x)(1-x+2x^2)&=&2+\frac{1}{4^2}\frac{1}{1-4x}-\frac{1}{4^2}-\frac{x}{4}\\
g(x)&=& \frac{x^2-8x+2}{(1-4x)(1-x+2x^2)} 
\end{eqnarray*}
How do I go from here to get $y_n$ as a complete solution, and also I noticed that $(1-x+2x^2)$ has imaginary roots, what does it mean? no solution?

Use the technique in Wilf's "generatingfunctionology" Define the generating function $A(z) = \sum_{n \ge 0} y_n z^n$, and write:
$$
y_{n + 2} = y_{n + 1} - 2 y_n + 4^n \quad y_0 = 2, y_1 = 1
$$
Using properties of generating functions:
$$
\frac{A(z) - y_0 - y_1 z}{z^2}
  = \frac{A(z) - y_0}{z} - 2 A(z) + \frac{1}{1 - 4 z}
$$
Solving for $A(z)$, reducing to partial fractions:
$$
A(z) = \frac{17z - 27}{14 (1 - z + 2 z^2)} + \frac{1}{14} \frac{1}{1 - 4 z}
$$
The first term's denominator splits into:
$$
\left( 1 - \frac{1 + i \sqrt{7}}{2} z \right)
   \left(1 - \frac{1 - i \sqrt{7}}{2} z \right)
$$
This gets quite ugly, and sadly the magnitude of those is also 4. This gives a solution that fluctuates wildly. The full solution is of the form:
$$
y_n = \alpha \left(\frac{1 + i \sqrt{7}}{2}\right)^n
        + \overline{\alpha} \left(\frac{1 - i \sqrt{7}}{2}\right)^n
        + \frac{4^n}{14}
$$
for some complex constant $\alpha$.
