I am trying to solve the following nonhomogeneous recurrence relation.

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.

  • $\begingroup$ 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. $\endgroup$ – dxiv Apr 7 '17 at 22:07
  • $\begingroup$ $$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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.