Generating function for a recurrence: I made a mistake

Question

Use generating functions to solve the recurrence $$a_n = 3a_{n-1} - 4a_{n-3} + n3^n$$ where $a_0 = a_1 = 1$, $a_2 = 0$.

I tried to solve this like any other generating functions problem, but I'm getting the wrong answer. Some, but not all, of the terms in the final partial fraction expansion are correct; the others are slightly off. (I tried using characteristic equations and I got the right answer, but I have to use generating functions.) Where am I going wrong?

My attempt: $$ \begin{align*} a_n &= 3a_{n-1} - 4a_{n-3} + n3^n \\ \implies \sum_{n=3}^{\infty} a_nx^n &= \sum_{n=3}^{\infty} 3a_{n-1}x^n - \sum_{n=3}^{\infty} 4a_{n-3}x^n + \sum_{n=3}^{\infty} n3^nx^n \\ \implies G(x) - a_0 - a_1x - a_2x^2 &= 3x\sum_{n=2}^{\infty} a_{n}x^n - 4x^3\sum_{n=0}^{\infty} a_{n}x^n + \sum_{n=3}^{\infty} n3^nx^n \\ &= 3x(G(x) - a_0 - a_1x) - 4x^3G(x) + \sum_{n=3}^{\infty} n3^nx^n \\ \implies G(x)(1 - 3x + 4x^3) &= (a_2 - 3a_1)x^2 + (a_1 - 3a_0)x + a_0 + \sum_{n=3}^{\infty} n3^nx^n \\ &= -3x^2 - 2x + 1 + \sum_{n=3}^{\infty} n3^nx^n \end{align*} $$ and as $\frac{3x}{(1-3x)^2} = \sum_{n=0}^{\infty} n3^nx^n$, we have $\sum_{n=3}^{\infty} n3^nx^n = \frac{3x}{(1-3x)^2} - 3x - 18x^2$ and $$ \begin{align*} G(x)(1 - 3x + 4x^3) &= -21x^2 - 5x + 1 + \frac{3x}{(1 - 3x)^2} \\ &= \frac{1 - 5x - 21x^2}{(2x - 1)^2(x + 1)} + \frac{3x}{(1 - 3x)^2(2x - 1)^2(x + 1)} \end{align*} $$

Decomposing that into partial fractions gives $$-\frac{57}{2(2 x - 1)} + \frac{513}{16 (3 x - 1)} - \frac{1}{2 (2 x - 1)^2} + \frac{27}{4 (3 x - 1)^2} - \frac{27}{16 (x + 1)}$$

However, the given answer (which I verified to be true) is $$-\frac{28}{2 x - 1} + \frac{405}{16 (3 x - 1)} - \frac{1}{2 (2 x - 1)^2} + \frac{27}{4 (3 x - 1)^2} - \frac{27}{16 (x + 1)}$$

Where did I go wrong?

Answer 1

The answer you got is right; the given answer is wrong. To easily check this, you can substitute $x=0$ in the second answer to get $$-\frac{28}{2\cdot0 - 1} + \frac{405}{16 (3\cdot0 - 1)} - \frac{1}{2 (2\cdot0 - 1)^2} + \frac{27}{4 (3\cdot0 - 1)^2} - \frac{27}{16 (0 + 1)} = \frac{29}{4}$$ which should be equal to $a_0 = 1$ but isn't.

It is true that the formula for $a_n$ is $$a_n = 28(2^n) - \frac{405}{16}(3^n) - \frac12 (n 2^n) + \frac{27}{4} (n 3^n) - \frac{27}{16}((-1)^n)$$ which appears to match the coefficients in the second answer. But the coefficients in the formula don't correspond to the coefficients in the partial fraction decomposition, because the terms which give you $n 2^n$ and $n 3^n$ are slightly more complicated: $$\frac{1}{(2x-1)^2} = \sum_{n=0}^\infty (n+1)2^n x^n$$ and $$\frac{1}{(3x-1)^2} = \sum_{n=0}^\infty (n+1)3^n x^n.$$

So from your (correct) partial fraction decomposition, you should actually obtain a coefficient of $\frac{57}{2} - \frac12 = 28$ for $2^n$ and a coefficient of $-\frac{513}{16} + \frac{27}{4} = -\frac{405}{16}$ for $3^n$, which matches the correct formula for $a_n$.