Particular solution of a non-homogenous recurrence relation I need some help with the following non-homogenous recurrence relation.
$$a_n-2a_{n-1}+a_{n-2}=n+1$$ 
$$a_0=0, a_1=1$$
When I solve the associated homogenous equation I use the auxiliary equation $x^2-2x+1=0$ and obtain the root $x=1$. Hence, I obtain the equation $a_n=(A+nB)1^n$. Using the initial conditions I get $a_n=n$.
When it comes to the particular solution I get stuck, however. I thought the solution should be on the form $cn+d$ due to $n+1$. The following calculations show how I then get stuck:
$$a_n-2a_{n-1}+a_{n-2}=n+1$$
$$cn+d-2(c(n-1)+d)+c(n-2)+d=n+1$$
$$cn+d-2(cn-c+d)+cn-2c+d=n+1$$
$$cn+d-2cn+2c-2d+cn-2c+d=n+1$$
$$0=n+1$$
So obviously I am wrong about the form of the particular solution.
 A: The form of the equation allows us to solve it by using only first-order difference equations (see Remark 1).
Arrange the equation as
$$\begin{cases}[a_{n}-a_{n-1}]-[a_{n-1}-a_{n-2}]=n+1,{\quad}n=3,4,\cdots\\ a_{1}=1,\ a_{0}=0,\end{cases}$$
which is a first-order difference equation in $b_{n}:=[a_{n-1}-a_{n-2}]$ for $n=2,3,\cdots$.
So, we have
$$\begin{cases}b_{n+1}-b_{n}=n+1,{\quad}n=2,3,\cdots\\ b_{2}=1,\end{cases}$$
which implies
$$\begin{aligned}b_{n}=&1\prod_{k=2}^{n-1}1+\sum_{k=2}^{n-1}(k+1)\prod_{\ell=k+1}^{n-1}1\\ =&1+\sum_{k=2}^{n-1}(k+1)\\ =&\sum_{{\color{blue}k=1}}^{n-1}k+(n-2)\\ =&\frac{1}{2}(n^{2}+n-4),\end{aligned}$$
where we have applied Remark 2(i).
Next, we set $c_{n}:=a_{n-2}$ for $n=2,3,\cdots$, then $c_{n+1}-c_{n}=a_{n-1}-a_{n-2}=b_{n}$, i.e.,
$$\begin{cases}c_{n+1}-c_{n}=\frac{1}{2}(n^{2}+n-4),{\quad}n=2,3,\cdots\\ c_{2}=0\end{cases}$$
whose solution is
$$\begin{aligned}c_{n}=&0\prod_{k=2}^{n-1}1+\frac{1}{2}\sum_{k=2}^{n-1}(k^{2}+k-4)\prod_{\ell=k+1}^{n-1}1\\ =&\frac{1}{2}\sum_{k=2}^{n-1}(k^{2}+k-4)\\ =&\frac{1}{2}\sum_{{\color{blue}k=1}}^{n-1}k^{2}+\frac{1}{2}\sum_{{\color{blue}k=1}}^{n-1}k-2(n-2)-{\color{blue}1}\\
=&\frac{1}{2}\frac{1}{6}(n-1)n(2n-1)+\frac{1}{2}\frac{1}{2}(n-1)n-2(n-2)-1\\ =&\frac{1}{6}(n^{3}-13n+18),\end{aligned}$$
where we have applied Remark 2(ii).
As $a_{n}=c_{n+2}$, we get
$$a_{n}=\frac{1}{6}(n^{3}+6n^{2}-n),{\quad}n=2,3,\cdots.\tag*{$\blacksquare$}$$
Remark 1. The first-order difference equation
$x_{n+1}-p_{n}x_{n}=q_{n}$
has the solution
$\displaystyle x_{n}=x_{m}\prod_{k=m}^{n-1}q_{k}+\sum_{k=m}^{n-1}q_{k}\prod_{\ell=k+1}^{n-1}p_{\ell}$
with the convention that the empty product is unity.
Remark 2. The following identities hold.
(i) $\displaystyle\sum_{k=1}^{m}k=\frac{1}{2}m(m+1)$.
(ii) $\displaystyle\sum_{k=1}^{m}k^{2}=\frac{1}{6}m(m+1)(2m+1)$.
A: Use difference solution. Define $\Delta a_k=a_k-a_{k-1}$:
$$
\Delta a_k- \Delta a_{k-1}=k+1\\
\Delta a_{k-1} - \Delta a_{k-2}=k\\
\ldots\\
\Delta a_2-\Delta a_1 = k-(k-3)
$$
Now sum LSH and RHS. On LHS you'll get $\Delta a_k - \Delta a_1$, on RHS $k(k-1)+1 - S_{k-3}$, where $S_{k-3} = 1+2+\ldots +k-3$. Clearly $\Delta a_1=1$ so you get 
$$
\Delta a_{k}= 2 +k(k-1)-S_{k-3}
$$
Now sum over $k$ over both sides. On LHS you'll get $a_n$ and on RHS some expression $O(n^3)$ after some algebra. Note $\frac{2k(k-1)}{2}-\frac{(k-3)(k-2)}{2}=\frac{k^2-3k-6}{2}.$
