generating functions, can't seem to get the correct answers. So, I've been having some issues with generating functions and counting problems. An example problem is: $$ a_n = a_{n-1} + 9a_{n-2} - 9a_{n-3} \;\;\; (n \geq 3)$$
Where $a_0 = 0, a_1 = 1, a_2 = 2$
Let's define $g(x)$ as our generating function, in which case, 
$$ g(x) = a_0 + a_1x + a_2x^2+... =  0 + x + 2x^2 + (a_2 + 9a_1 - 9a_0)x^3 + (a_3+9a_2-9a_1)x^4+...$$
We can factor this like so...
$$g(x) = x + 2x^2 + x(a_2x^2 + a_3x^3 + ...) +  9x^2(a_1x + a_2x^2+...) - 9x^3(a_0 + a_1x + a_2x^2+...)$$
Now, the infinite series, $a_2x^2 + a_3x^3+...$ can be defined as $g(x) - a_0 - a_1x$, and the series $a_1x + a_2x^2+...$ can be defined as $g(x) - a_0$, and lastly, the series $a_0 + a_1x + a_2x^2+...$ is $g(x)$
So, making substitutions:
$$g(x) = x + 2x^2 + xg(x) - x^2 + 9x^2g(x) - 9x^3g(x)$$
and finally, 
$$g(x) = \frac{x^2 + x}{9x^3 - 9x^2 - x + 1}$$
I decided to run this through wolfram alpha for the partial fraction decomposition and I get:
$$g(x) = \frac{1}{3}\left (\frac{1}{1+3x}\right ) + \frac{1}{12}\left (\frac{1}{1+3x}\right ) - \frac{1}{4}\left (\frac{1}{1+x}\right )$$
Each of the terms in parenthesis can be expressed as a series, in summation notation: 
$$\frac{1}{3}\sum_{k = 0}^{\infty }(-3)^kx^k + \frac{1}{12}\sum_{k = 0}^{\infty }(-3)^kx^k - \frac{1}{4}\sum_{k=0}^{\infty }(-1)^kx^k$$
And, my final answer should be:
$$a_n = \frac{1}{3}(-3)^n + \frac{1}{12}(-3)^n - \frac{1}{4}(-1)^n$$
Which, is incorrect. Could someone point out what I'm doing wrong?
 A: The partial fraction decomposition is not correct: Note that the expression in the denominator factors as $(3x-1)(3x+1)(x-1)$. Calculating by hand may be faster, and safer. 
A: Your partial fractions aren’t right. However, there’s an easier way to handle such problems.
Let $g(x)=\sum_{n\ge 0}a_nx^n$. be the generating function. With the convention that $a_n=0$ if $n<0$, we can write the recurrence as
$$a_n = a_{n-1}+9a_{n-2}-9a_{n-3}+[n=1]+[n=2]\;,\tag{1}$$
valid for all $n\ge 0$, where the last two terms are Iverson brackets; they ensure that the initial values are correct.
Now multiply $(1)$ by $x^n$ and sum over $n$ to get
$$\begin{align*}
g(x)&=\sum_{n\ge 0}a_nx^n\\
&=\sum_n(a_{n-1}+9a_{n-2}-9a_{n-3}+[n=1]+[n=2])x^n\\
&=\sum_n a_{n-1}x^n+9\sum_n a_{n-2}x^n-9\sum_n a_{n-3}x^n+x+x^2\\
&=x\sum_n a_nx^n+9x^2\sum_n a_nx^n-9x^3\sum_n a_nx^n+x+x^2\\
&=g(x)\left(x+9x^2-9x^3\right)+x+x^2\;,
\end{align*}$$
so 
$$\begin{align*}g(x)&=\frac{x+x^2}{1-x-9x^2+9x^3}\\
&=\frac{x+x^2}{(1-x)(1-3x)(1+3x)}\\
&=\frac{-1}{4(1-x)}+\frac1{3(1-3x)}-\frac1{12(1+3x)}\\
&=-\frac14\sum_{n\ge 0}x^n+\frac13\sum_{n\ge 0}3^nx^n-\frac1{12}\sum_{n\ge 0}(-1)^n3^nx^n\;,
\end{align*}$$
and 
$$\begin{align*}
a_n&=-\frac14+3^{n-1}-\frac14(-1)^n3^{n-1}\\
&=3^{n-1}-\frac14\left(1+(-1)^n3^{n-1}\right)\;.
\end{align*}$$
A: A simpler way, due to Wilf:
Your recurrence is $a_{n + 3} = a_{n + 2} + 9 a_{n + 1} - 9 a_n$. If you multiply by $x^n$ and add for $n \ge 0$ it is:
$$
\begin{align*}
\sum_{n \ge 0} a_{n + 3} x^n
   &= \sum_{n \ge 0} a_{n + 2} x^n + 9 \sum_{n \ge 0} a_{n + 1} x^n - 9 \sum_{n \ge 0} a_n x^n \\
\frac{g(x) - a_0 - a_1 x - a_2 x^2}{x^3}
   &= \frac{g(x) - a_0 - a_2 x}{x^2} + 9 \frac{g(x) - a_0}{x} - 9 g(x)
\end{align*}
$$
As you see, it is almost immediate to write the last equation just by looking at the recurrence. A term $a_{n + k}$ gives rise to
$$
\frac{g(x) - a_0 - a_1 x - \ldots - a_{k - 1} x^{k - 1}}{x^k}
$$
The rest, as they say, is algebra (a computer algebra package like maxima helps a lot) and a bit of series expansion.
