2
$\begingroup$

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?

$\endgroup$
4
+50
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Then why isn't it matching with WolframAlpha? (after multiplying out the coefficients of the exponentials) $\endgroup$ – shardulc Mar 23 '17 at 4:24
  • 2
    $\begingroup$ 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. $\endgroup$ – Misha Lavrov Mar 23 '17 at 4:35
  • $\begingroup$ Thanks! I completely missed the $n + 1$ part, should remember that from now onwards :P $\endgroup$ – shardulc Mar 23 '17 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.