Solving recurrence equation with generating functions $$a_{0}=0$$
$$a_{1}=0$$
$$a_{2}=-1$$
$$a_{n+3}-6a_{n+2}+12a_{n+1}-8a_{n}=n$$
It's just that...I don't know what to do if there are $a_{n+1}$ instead of $a_{n-1}$, I don't know what to do with that $n$...How can I solve this?
 A: We are given $$a_{n+3}-6a_{n+2}+12a_{n+1}-8a_n=n.$$ Increasing $n$ by one gives us $$a_{n+4}-6a_{n+3}+12a_{n+2}-8a_{n+1}=n+1.$$ Subtracting these two equations yields $$a_{n+4}-7a_{n+3}+18a_{n+2}-20a_{n+1}+8a_n=1,$$ so we will focus on solving this recurrence relation. First we find the general homogenous solution, i.e. the general solution to $$a_{n+4}-7a_{n+3}+18a_{n+2}-20a_{n+1}+8a_n=0.$$ This is a linear recurrence with characteristic equation $$x^4-7x^3+18x^2-20x+8=(x-2)^3(x-1)=0,$$ which we know to have the general solution $a_n=2^n(n^2+an+b)+c$. To find a particular solution we first note that $n-6n+12n-8n=-n$, so make the Ansatz $a_n=-n+d$. Substituting into $$a_{n+3}-6a_{n+2}+12a_{n+1}-8a_n=n$$ gives an equation for $d$, which is solved by $d=-3$, so our general solution is $$a_n=a_n=2^n(n^2+an+b)+c-n-3.$$ Substitute the three initial conditions and solve for $a$, $b$ and $c$ to get the solution.
A: Let $f(x) =\sum_{n=0}^{\infty} a_n x^n$.  Usually relations like
$$a_{n+3}-6a_{n+2}+12a_{n+1}-8a_{n}=n$$
come with a restriction on n.  I'm going to assume the equation holds for all $n \ge 0$.
Multiply by $x^n$:
$$a_{n+3} x^n-6a_{n+2}x^n+12a_{n+1}x^n-8a_{n}x^n=n x^n$$
Sum over $n= 0, 1, 2, \dots$:
$$\sum_{n=0}^{\infty} a_{n+3} x^n-6\sum_{n=0}^{\infty} a_{n+2}x^n+12\sum_{n=0}^{\infty} a_{n+1}x^n-8\sum_{n=0}^{\infty} a_{n}x^n=\sum_{n=0}^{\infty} n x^n$$
To deal with a sum like $\sum_{n=0}^{\infty} a_{n+1} x^n$, for example, observe that
$$x \sum_{n=0}^{\infty} a_{n+1} x^n = \sum_{n=0}^{\infty} a_{n+1} x^{n+1}= \sum_{n=1}^{\infty} a_n x^n = f(x) - a_0$$
so
$$\sum_{n=0}^{\infty} a_{n+1} x^n = \frac{f(x)-a_0}{x}$$
Maybe you can handle the rest?
