General Solution for a non-Homogeneous Recurrence 
What is the general solution to the recurrence:
  $$x(n + 2) = x(n + 1) + x(n) + n - 1$$
  where $n\geq 1$ with $x(1) = 0, x(2) = 1$?

It's a question on a practice exam I'm reviewing and I'm not quite sure why my solution is incorrect.
So I went through the characteristic equation and found the constants, and the solution to the homogeneous part of this question is:
$$x(n) = \frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{\sqrt{5}}$$
This is the Fibonacci expression, right? So, what do I do with the non-homogeneous part of the expression? My professor mentioned something about solving them separately but I'm not sure what to do with it now.
 A: Let $y_n = x_n + n$. Then the equation becomes $y_{n+2} = y_{n+1}+y_n$. Now, solve for $y_n$ using usual method.
A: Solution Using Method of Annihilators
Let $E$ denote the "shift" operator, and let $\langle x_n \rangle$ denote the sequence $x_1, x_2, x_3, \ldots$
Then our recurrence can be re-written as:
$$x_{n+2} - x_{n+1} - x_n = n - 1 \iff (E^2-E-1)\langle x_n\rangle = \langle n-1\rangle$$
The annihilator for $n-1$ is $(E-1)^2$, we have:
$$(E-1)^2(E^2-E-1)\langle x_n\rangle = (E-1)^2\langle n-1\rangle=\langle 0\rangle$$
So, we've now converted our problem from a non-homogenous problem to a homogeneous problem; the only difficulty is that we have also changed the recurrence from a $2$nd order recurrence to a $4$th order recurrence. Thus, we need to compute two more initial conditions:
\begin{align}
x_2 &= 1\\
x_3 &= 3
\end{align}
We can easily move from the annihilator operator form to the characteristic of this fourth-order recurrence:
$$(r-1)^2(r^2-r-1) \implies r=1, 1, \frac{1+\sqrt 5}{2}, \frac{1-\sqrt 5}{2}$$
Thus, our general solution has the form:
$$x_n = A + Bn + C\left(\frac{1+\sqrt 5}{2}\right)^n + D\left(\frac{1-\sqrt 5}{2}\right)^n$$
Using our four initial conditions, we find:
\begin{align}
x_1 &= 0 = A +  B + \left(\frac{1+\sqrt 5}{2}\right)C   + \left(\frac{1-\sqrt 5}{2}\right)D\\
x_2 &= 1 = A + 2B + \left(\frac{1+\sqrt 5}{2}\right)^2C + \left(\frac{1-\sqrt 5}{2}\right)^2D\\
x_3 &= 1 = A + 3B + \left(\frac{1+\sqrt 5}{2}\right)^3C + \left(\frac{1-\sqrt 5}{2}\right)^3D\\
x_4 &= 3 = A + 4B + \left(\frac{1+\sqrt 5}{2}\right)^4C + \left(\frac{1-\sqrt 5}{2}\right)^4D\\
\end{align}
This is a system of linear equations; using any method, we arrive at the solution $A = 0, B=-1, C=1, D = 1$.
Thus, the solution is:
$$x_n =\left(\frac{1+\sqrt 5}{2}\right)^n + \left(\frac{1-\sqrt 5}{2}\right)^n - n$$
For what it's worth, the first several values of the sequence are:
1 |  0
2 |  1
3 |  1
4 |  3
5 |  6
6 | 12
7 | 22
8 | 39
9 | 67

A: Hint: $x^2 - x - 1 = 0 \to x = \dfrac{1\pm \sqrt{5}}{2}$. Let $x_h = A\left(\dfrac{1+\sqrt{5}}{2}\right)^n + B\left(\dfrac{1-\sqrt{5}}{2}\right)^n$ be the homogeneous solution, and $x_p = Cn + D$ be the particular solution, then the general solution is:
$x_n = x_h + x_p$.
A: Generating Function Approach
The below recurrence is equivalent to the recurrence in the OP, but has been extended to allow $n=0$:

$$a_{n+2} = a_{n+1} + a_n + n - 1\tag{$\star$}$$
  for $n\geq 2$, and $a_0=2, a_1=0$.

Define $A(x) = \sum_{n=0}^\infty a_n x^n$.  Then, multiplying $(\star)$ by $x^n$ and summing over $n$, we have: (note: all sums are to be taken as $\sum_{n=0}^\infty$, but I'm leaving off the limits for ease of typing.)
$$\sum_n a_{n+2}x^n = \sum_na_{n+1}x^n+\sum_n a_n x^n + \sum_n(n-1)x^n\tag{$\star\star$}$$
We can rewrite $(\star\star)$ as:
$$\frac{A(x)-2}{x^2}-\frac{A(x)-2}{x} -A(x) = \sum_n (n-1)x^n = \frac{2x-1}{(1-x)^2}$$
Rearranging the above, we have:
$$A(x)\frac{1-x-x^2}{x^2}=\frac{2-2x}{x^2}+\frac{2x-1}{(1-x)^2}$$
Thus, 
\begin{align}A(x) &= \frac{2(1-x)}{1-x-x^2} + \frac{2x^3-x^2}{(1-x-x^2)(1-x)^2} \\
&= \frac{5 x^2-6 x+2}{(1-x-x^2)(1-x)^2} \\
&= \frac{x-2}{x^2 + x - 1} -\frac{1}{(x-1)^2} - \frac{1}{x-1}
\end{align}
The Taylor Series for each of the above can be found (albeit the first term takes some work), then the coefficient of $x^n$ is the $n$th term.
