Solve the recursion, $a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$ 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?
 A: 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.
A: To expand one of the comments, if $A_n$ is a solution of the homogeneous part $$A_n=3A_{n-1}-3A_{n-2}+A_{n-3}$$ and $B_n$ satisfies $$B_n=3B_{n-1}-3B_{n-2}+B_{n-3}+8$$ then $kA_n+B_n$ satisfies the original recurrence.
The characteristic polynomial of the homogeneous part is $(x-1)^3$. I have given some answers to questions similar in content going into a clunky form of why the following works - generating functions give the same answer, and a sound proof - $A_n=(pn^2+qn+r)1^n$ where $p, q, r $ are arbitrary, and I've emphasised $1^n (=1)$ because it would be $2^n$ if the generating function had a factor $(x-2)^3$, and it would be a cubic in $n$ if it were $(x-\alpha)^4$ (etc).
The difficulty then arises because the inhomogeneous part $8=8\times 1^n$, and $1$ is a solution of the characteristic polynomial, so the obvious test function $B_n=constant$ won't work. In fact, because $A_n$ involves a quadratic, it is the next highest power you test: $B_n=kn^3$ to find the value of $k$.
As I say, generating functions will get you there, as will other methods, if you want to prove the method works. On the other hand, if you want to identify a solution quickly, it is useful to know which functions to test. $A_n+B_n$ has three parameters $p, q, r$ which determine the sequence, and these correspond to the three values of $a_n$ which are required to do the same. So, given the initial values (or three values of $a_m$), it is easy to show that the solution is unique. The test functions I have suggested work, so they provide the solution.
Do try it out, because the theory all hangs together.
A: Rewrite the expression for simplicity as 
$$
a_{k+3}=3 a_{k+2} -3 a_{k+1} +a_k +8
$$
Multiply by $z^k$ and sum over $k$ to get the generating function $G(z)=\sum_{k \geq 0}a_k z^k$. On LHS you'll get 
$$
\frac{1}{z^3}\bigg(G(z)-a_0 -a_1 z -a_2 z^2\bigg)
$$
On RHS you get 
$$
\frac{3}{z}\bigg(G(z)-a_0\bigg)-\frac{3}{z^2}\bigg(G(z)-a_0-a_1 z\bigg)+G(z)+\frac{8}{1-z}
$$
Now do the algebra carefully to get on LHS $G(z)$ and on RHS some expression of the form $\sum_{k=0}^{\infty}\varphi_k z^k$. Can you handle from here?
