I am trying to solve the following nonhomogeneous recurrence relation.
$a_n=\frac{1}{2}a_{n-1}+\frac{1}{2}a_{n+1}+1$
I know the general solution is of the form $-x^2+mx+n$, but I can't seem to derive it for the life of me. I haven't had to solve one of these in ages. My first stab at it got me this far:
First I rewrote the relation to get rid of the $a_{n+1}$ term, so I have
$a_{n-1}=\frac{1}{2}a_{n-2}+\frac{1}{2}a_{n}+1$
The associated characteristic equation is $\frac{1}{2}r^2-r+\frac{1}{2}=0$, whose solution is $r=1$. Then $a_n=c*1^{n}=c.$ This seems totally wrong to me. No idea how to gather a particular solution from here either. Any help would be appreciated.
Best Answer
My idea is to rewrite the equation as the following two equations: $$a_{n+1} = 2a_n-a_{n-1}-2$$ $$a_n = 2a_{n-1}-a_{n-2}-2$$ Subtracting these two, we get $a_{n+1}=3a_n-3a_{n-1}+a_{n-2}$, so the characteristic polynomial is $$r^3-3r^2+3r-1=(r-1)^3$$ Hence the solution to this recurrence equation is $$a_n=\left(c_1+c_2\cdot n+ c_3\cdot n^2\right)\cdot 1^n = c_1+c_2\cdot n+ c_3\cdot n^2$$ where the constants $c_1$, $c_2$, $c_3$ are determined by initial values.