The relation is:
$$a_n=a_{n-1}-2a_{n-2}+4^{n-2}$$ $$a_0=2, a_1=1$$
I managed to reduce the problem to the generating function:
$$A(x)=\frac{2-9x+5x^2}{(1-4x)(1-x+2x^2)}$$
and then I got this:
$$A(x)=\frac{1}{14}\left(\frac{27-17x}{2x^2-x+1}-\sum\limits_{n=1}^\infty(-1)4^nx^n\right)$$
How can I write the remaining fraction as a series so I can solve the recurrence relation?
It's not going to be particularly pretty, but the standard way (as is done with the Fibonacci sequence, for example) is to let $$ 2x^2 - x + 1 = (x - \alpha) (x - \beta) $$ for complex $\alpha, \beta$ (it will probably save you work to name them $\alpha$ and $\beta$ rather than giving them explicitly with the quadratic formula). Then solve the partial fractions decomposition $$ \frac{27x - 17}{2x^2 - x + 1} = \frac{A}{x - \alpha} + \frac{B}{x - \beta} $$ and you should end up with a representation $$ a_n = c_1 \alpha^n + c_2 \beta^n + c_3 4^n. $$ Of course, you can solve for $c_1, c_2, c_3$ directly by plugging in a few values of $n$.