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?
 A: 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.
A: 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$.
A: Once you have $g(x)$ as a rational function (quotient of two polynomials), you can use the partial fractions technique you may have learned if you studied Calculus to write that rational function as (in your case) a sum of terms each of the form $${A\over1-\beta x}$$ Then you can expand each of those terms as a geometric series, $${A\over1-\beta x}=\sum_0^{\infty}A\beta^nx^n$$ and you will wind up with a generating function whose coefficients are of the form $$A_1\beta_1^n+A_2\beta_2^n+\cdots+A_r\beta_r^n$$ and there is your solution. 
