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