# 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

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