<s>[INST] 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.
 [/INST] 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.
</s>