Bring the following recursion relation to an explicit expression:
$$a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$$
$a_{0} = 0$, $a_1 = 1$, $a_2 = 2$
All the examples I have seen were with maximum 2 steps back ($a_{n-2}$) and I thought I know how to solve those but I'm having a hard time both with the Generating function and the Characteristic polynomial methods.
The Generating function should start from $n = 3$ but what would happen to the defined values?
For the Characteristic polynomial, Does it mean I'll have to find the roots of a polynomial from a 3rd degree?
Best Answer
If you use the characteristic polynomial, it will indeed be a cubic, but it’s a cubic that factors very easily: it’s
$$x^3-3x_2+3x-1=(x-1)^3\;.$$
If you use generating functions, note that you can write the recurrence as
$$a_n=3a_{n-1}-3a_{n-2}+a_{n-3}+8-8[n=0]-7[n=1]-9[n=2]\;,\tag{1}$$
valid for all $n\in\Bbb Z$ if you make the blanket assumption that $a_n=0$ for all $n<0$. The last three terms are Iverson brackets and are there to make the recurrence yield the correct initial values.
Now multiply $(1)$ by $x^n$ and sum over $n\ge 0$:
$$\sum_{n\ge 0}a_nx^n=3\sum_{n\ge 0}a_{n-1}x^n-3\sum_{n\ge 0}a_{n-2}x^n+\sum_{n\ge 0}a_{n-3}x^n+8\sum_{n\ge 0}x^n-8-7x-9x^2\;.\tag{2}$$
If the generating function is $A(x)$, $(2)$ can be rewritten as
$$A(x)=3xA(x)-3x^2A(x)+x^3A(x)+\frac8{1-x}-8-7x-9x^2\;,$$
which you can then solve for $A(x)$ and resolve into partial fractions.