Solving recurrence equation using generating functions

Question

$$a_{0} = 0, a_{1} = 1, a_{2} = 2, a_{3} = 6$$ $$a_{n} = a_{n+3} - a_{n+2}$$
$\sum = a_{n}x^{n}$
$A(x) = \frac{A(X) - x - 2x^{2}}{x^{3}} - \frac{A(x) - x}{x^{2}}$
$A(x) = \frac{x^{3} + x - 1}{-x^{2} - x}$

Is this the correct solution? The answer is different as far as I know, why is that so? Is it needed to replace the recurrence equation with minuses after n's? (well, all examples I've seen are with minuses there) And if so, how can I do this?

Answer 1

If we make a blanket assumption that $a_n=0$ for all $n<0$, we can write the recurrence as

$$a_n=a_{n-1}+a_{n-3}+[n=1]+[n=2]+4[n=3]\;,\tag{1}$$

where the last three terms are Iverson brackets, and it will be correct for all $n\ge 0$.

If you’ve not seen this idea before, try evaluating $(1)$ for $n=0,1,2,3$ on the assumption mentioned at the beginning: $$\begin{align*}&a_0=a_{-1}+a_{-3}+0+0+4\cdot0=0\\&a_1=a_0+a_{-2}+1+0+4\cdot0=1\\&a_2=a_1+a_{-1}+0+1+4\cdot0=2\,\text{ and}\\&a_3=a_2+a_0+0+0+4\cdot1=6\;.\end{align*}$$

Multiplying through by $x^n$ and summing over $n\ge 0$, we get the generating function:

$$\begin{align*} A(x)&=\sum_{n\ge 0}a_nx^n\\ &=\sum_{n\ge 0}\Big(a_{n-1}+a_{n-3}+[n=1]+[n=2]+4[n=3]\Big)x^n\\ &=\sum_{n\ge 0}a_{n-1}x^n+\sum_{n\ge 0}a_{n-3}x^n+x+x^2+4x^3\\ &=xA(x)+x^3A(x)+x+x^2+4x^3\;, \end{align*}$$

so

$$A(x)=\frac{x+x^2+4x^3}{1-x-x^3}\;.$$

I find this method the easiest way to account for the initial values correctly.