# Finding general solutions to recurrences

What is the general solution to the recurrence

$$x_{n+2} = x_{n+1} + x_n + n-1$$ for $n\ge 1$ with $x_1 = 0$, $x_2=1$?

I am stuck on this a bit. Can someone help me understand this?

-
I've edited your post to include MathJax. Please verify that it still says what you intended. –  user61527 Nov 26 '13 at 3:35
Thank you. that would work –  Rajen Nov 26 '13 at 3:37

First, note that $c_n=-n$ satsifies the recurrence equation.

So $y_n=x_n-c_n$ satisfies the homogeneous recurrence equation :

$$y_{n+2}=y_{n+1}+y_n$$

The characteristic polynomial of this is $X^2-(X+1)$, whose roots are $\frac{1\pm \sqrt{5}}{2}$.

So there are two constant $c_1$ and $c_2$ such that $$y_n=c_1\big(\frac{1-\sqrt{5}}{2}\big)^n+c_2\big(\frac{1+\sqrt{5}}{2}\big)^n$$

We then have

$$\begin{array}{lccl} 1&=&y_1&=&c_1\big(\frac{1-\sqrt{5}}{2}\big)+c_2\big(\frac{1+\sqrt{5}}{2}\big), \\ 3&=&y_2&=&c_1\big(\frac{1-\sqrt{5}}{2}\big)^2+c_2\big(\frac{1+\sqrt{5}}{2}\big)^2 \\ \end{array}$$

Solving this system, we find $c_1=c_2=1$. Finally

$$x_n=-n+(\frac{1-\sqrt{5}}{2}\big)^n+\big(\frac{1+\sqrt{5}}{2}\big)^n$$

-