# Generating function for a recurrence: I made a mistake

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?

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$.
• I think you're going wrong in the final step: going from the partial fraction decomposition to the coefficients. Keep in mind that the coefficient of $x^n$ in $\frac1{(3x-1)^2}$ is not $n3^n$ but $(n+1)3^n$, so that term will contribute both to the coefficient of $n3^n$ and to the coefficient of $3^n$. I'll edit the solution to elaborate on this. Mar 23, 2017 at 4:35
• Thanks! I completely missed the $n + 1$ part, should remember that from now onwards :P Mar 23, 2017 at 4:57