Solving Another Recursion Using Generating Functions I am trying to find a closed form for 

$$
Y(n) = Y(n-1) -2Y(n-2) + 4^{n-2} \text{ with initial conditions } Y(0) = 2,Y(1) = 1
$$ 

using generating functions.  However, I am still not entirely sure how the process works.  Will I always want to choose some series $A(x) = \sum a_nx^n$ to substitute for $Y(n)$ and remove successive terms as necessary to get the $Y(n-1)$ and $Y(n-2)$ terms?  Are there other choices for functions, or other tricks to be aware of?
 A: Let $A(x):=\sum_{n\ge 0} Y_n\,x^n$. Then we have
$$A(x)= 2+x+\sum_{n\ge 2} (Y_{n-1}-2Y_{n-2}+4^{n-2})x^n= \\
= 2+x+\sum_{n\ge 2} Y_{n-1}x\cdot x^{n-1}-2\sum_{n\ge 2}Y_{n-2}x^2\cdot x^{n-2}+\sum_{n\ge 2}4^{n-2}x^2\cdot x^{n-2} = \\
= 2+x+(x\cdot A(x)-2x)-2x^2\cdot A(x)+x^2\cdot\sum_{k\ge 0}(4x)^k = \\
= 2-x+(x-2x^2)\cdot A(x)+\frac{x^2}{1-4x} \,.
$$
From this, $A(x)$ is expressible, then find its Taylor series.
A: Use Wilf's "generatingfunctionology" techniques: Write:
$$
Y_{n + 2} = Y_{n + 1} - 2 Y_n + 4^n \quad Y_0 = 2, Y_1 = 1
$$
Define the ordinary generating function:
$$
A(z) = \sum_{n \ge 0} Y_n z^n
$$
By properties of ordinary generating functions, as $\sum_{n \ge 0} 4^n z^n = (1 - 4 z)^{-1}$:
$$
\frac{A(z) - Y_0 - Y_1 z}{z^2} = \frac{A(z) - Y_0}{z} - 2 A(z) + \frac{1}{1 - 4 z}
$$
Substituting the values of $Y_0$, $Y_1$, written as partial fractions:
$$
A(z) = \frac{27 - 14 z}{14 (1 - z + 2 z^2)} + \frac{1}{14} \frac{1}{1 - 4 z}
$$
Unfortunately the first denominator has complex roots, the second one is just a geometric series.
