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?