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

Question

I am currently solving a recurrence relation but I got stuck since I am not even able to find the basic root of the auxiliary equations.

Answer 1

Let's rewrite this as \begin{align*} a_{n+3} = a_{n+2} + 2(n+3) + 3a_n \end{align*} The generating function for this sequence is \begin{align*} \frac{f(x) - a_0 - a_1x - a_2x^2}{x^3} = \frac{f(x) - a_0 - a_1x}{x^2} + \frac{2(3 - 2x)}{(1-x)^2} + 3f(x) \end{align*} Solving for $f(x)$ gives us \begin{align*} f(x) = \color{blue}{\frac{a_0(x-1)}{(3x^3+x-1)}} + \color{red}{\frac{a_1 x(x-1)}{(3x^3+x-1)}} - \color{green}{\frac{a_2x^2}{(3x^3+x-1)}} - \color{orange}{\frac{2(3-2x)x^3}{(x-1)^2(3x^3+x-1)}} \end{align*} Let $r_1, r_2, r_3$ be the roots of $3x^3 + x - 1=0$. Then the series expansion of the blue term is \begin{align*} \sum_{n=0}^{\infty}\underbrace{\left\{\frac{a_0}{3}\left(\frac{1 - r_1}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + \frac{1 - r_2}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + \frac{1 - r_3}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}\right)\right\}}_{p_n}x^n \end{align*} Similarly, the red portion is \begin{align*} \sum_{n=0}^{\infty}\underbrace{\left\{\frac{a_1}{3}\left(\frac{r_1(1 - r_1)}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + \frac{r_2(1 - r_2)}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + \frac{r_3(1 - r_3)}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}\right)\right\}}_{q_n}x^n \end{align*} The green portion is \begin{align*} \sum_{n=0}^{\infty}\underbrace{\left\{\frac{a_2}{3}\left(\frac{r_1^2}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + \frac{r_2^2}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + \frac{r_3^2}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}\right)\right\}}_{r_n}x^n \end{align*} Exercise Find the series expansion for the orange term, and call the coefficients as $s_n$.

Finally, your sequence can be expressed as \begin{align*} a_n = p_n + q_n - r_n - s_n \end{align*} There is some heavy simplification you can do. For example, you can express \begin{align*} p_n + q_n - r_n=\sum_{t=1}^{3}\frac{1}{r_t^{n+1}}g_t(a_0, a_1, a_2, r_1, r_2, r_3) \end{align*} For functions $g_1, g_2, g_3$, which you can pre-compute in a computer implementation.