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.
Best Answer
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)$.