<s>[INST] Solving recurrent equation $a_1=3; a_2=1; a_n = a_{n-1} + 2a_{n-2}+2$ I have the following recurrent equation
$
a_1=3\\a_2=1\\a_n=a_{n-1}+2a_{n-2}+2
$
and I cannot seem to be able to solve it correctly. According to wolframalpha and my math textbook (that contains results but not the actual process), the result should be $a_n=-2(-1)^n+2^n-1$, but I cannot seem to actually get that result and I cannot find where I am making a mistake.
My current approach (based on the textbook) is:
$a_{n=1} = 2$, needs to add 1.
$a_{n=2} = 5$, needs to substract 4.
The universal equation therefore is $a_n=a_{n-1}+2a_{n-2}+2+[n=1]-4[n=2]$.
$A(x)=xA(x) + 2x^2A(x)+2+x-4x^2$, divide both sides by $A(x)$:
$1= x + 2x^2 + {\frac {2+x-4x^2} {A(x)}}$, move $A(x)$ to one side:
$A(x) = {\frac {-4x^2+x+2} {-2x^2 -x +1}}$, divide the polynomials:
$A(x) = 2+{\frac {3x} {-2x^2-x+1}}$, split into multiple fractions:
$A(x) = 2+3x * \frac {1} {1-2x} * \frac {1} {1+x}$.
This is the point where I get lost, how exactly am I supposed to expand something like this into a power series? If I made a mistake in the process, could someone explain, why? Does anyone have other solutions for this problem?
Thanks a lot.
 [/INST] Well I would do like this. Since for all $n$ we have:
$$
a_n-a_{n-1}-2a_{n-2}=2 $$
we have also (change $n$ to $n+1$) $$a_{n+1}-a_{n}-2a_{n-1}=2$$
so if we substract these two we get: $$a_{n+1}-2a_n-a_{n-1}+2a_{n-2}=0$$
so zeroes of characteristic equation $x^3-2x^2-x+2=0$ are $1,2,-1$ so $$a_n = a\cdot (-1)^n+b\cdot 2^n+c\cdot 1^n$$
</s>