# 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.

-
You can't use inhomogeneous initial condition for homogeneous problem. – Kaster Nov 28 '13 at 17:34
Can you expand on that? – tychicus Nov 28 '13 at 17:47
You said that to find $a_n$ you use initial conditions, but you can't do that since initial conditions are from different inhomogeneous problem. – Kaster Nov 28 '13 at 18:31
If it doesn't work out, try a larger degree polynomial. – vonbrand Aug 21 '15 at 0:18

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}.$

-
Thank you for the help. – tychicus Dec 5 '13 at 16:35
You are welcome – Alex Dec 5 '13 at 16:40

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

-