# Solving a particular nonhomogeneous recurrence relation

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.

• solution is r=1 That's a double root, so $a_n=(c_0 + c_1 n)\cdot 1^n\,$ for the homogeneous part. Or, without characteristic polynomials, write the recurrence as $(a_{n+1}-a_n)=(a_n-a_{n-1}) - 2\,$ and telescope. – dxiv Apr 7 '17 at 22:07
• $$a_n = \frac 12 a_{n-1} + \frac12 a_{n+1} + 1$$ $$a_{n+1} = \frac 12 a_{n} + \frac12 a_{n+2} + 1$$ now subtract the first equation from the second. – DanielV Apr 8 '17 at 1:30

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.