Solve recurrence relation $a_n = 3 a_{n - 3} + a_{n-1} + 2 n$

Question

I am not able to solve the above recurrence relation which involves $n$. The initial conditions $a_0 = 1, a_1 = 2, a_2 = 3$, for $n \geq 0$. Please try to give closed form in terms of arbitrary $a_i \geq 1 $ for $i \geq 0$

Answer 1

Here is what you can do:

First write $a_{n+1}=3a_{n-2}+a_n+2n+2$ (I inserted $n=n+1$ to the equation) and subtract the original equation to obtain $a_{n+1}-a_n=3a_{n-2}-3a_{n-3}+a_n-a_{n-1}+2$ which is the same as $$a_{n+1}=2a_n-a_{n-1}+3a_{n-2}-3a_{n-3}+2$$

Now do the same trick again: $a_{n+2}=2a_{n+1}-a_n+3a_{n-1}-3a_{n-2}+2$ and subtract the above equation to obtain: $$a_{n+2}=3a_{n+1}-3a_n+4a_{n-1}-6a_{n-2}+3a_{n-3}$$ Now this is a homogenous recurrence relation. Since we increased the degree by $2$, we also need to compute $a_4$ and $a_5$ and then solve the equation via classical techniques.

Edit : To solve the relation completely, you first insert $x^n$ for $a_n$ to obtain the degree $5$ polynomial $x^5-3x^4+3x^3-4x^2+6x-3=0$. Then compute all the roots of this polynomial, say $x_1,\dots,x_5$. If they are all distinct, general solution of the relation is of the form $$c_1\cdot x_1^n+\dots+c_5\cdot x_5^n$$ for $c_i\in\mathbb{C}$ and you can compute $c_i$ by using the initial conditions. If there is a double root, say $x_1$, (in this case $1$ is a double root and there are $3$ distinct roots) then a general solution is of the form $$c_1\cdot x_1^n+c_2\cdot n x_1^n+c_3\cdot x_2^n+\dots+c_5\cdot x_4^n$$ and again, you can compute $c_i$ using the initial conditions.

Answer 2

Another solution

Take $a_n= b_n -\frac{2n}{3} -\frac{20}{9}$ and plug $a_n$ in the initial difference equation.

You find that $b_n = 3 b_{n - 3} + b_{n-1}$ which is a linear difference equation of order $3$.

So now to find the solution you still have to find the root of $p(x) = x^3-x^2-3$ if we want to use the "classical method".