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?

I get a slightly different result from you. Let
$$y(x) = \sum_{n=0}^{\infty} y_n x^n$$
Then, summing the recurrence relation from $n=2$ on, I get
$$y(x) - y_0 - y_1 x - x [y(x)-y_0] + 2 x^2 y(x) = \frac{x^2}{1-4 x}$$
Simplifying, using the initial conditions $y_0=2$ and $y_1=1$:
$$(2 x^2-x+1)y(x) = \frac{x^2}{1-4 x} + 2-x = \frac{5 x^2-9 x+2}{1-4 x}$$
Therefore the generating function is
$$y(x) = \frac{5 x^2-9 x+2}{(1-4 x)(2 x^2-x+1)}$$
Your concern about whether the denominator has complex roots is unfounded.  The roots of the quadratic in the denominator are based on the characteristic equation for the recurrence that leads to the homogeneous solution.  When the roots of this equation are complex, then there is both exponential growth and oscillatory behavior; this is quite normal.
