Finding general solutions to recurrences

Question

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?

Answer 1

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