Solving a third-order recurrence relation

Question

How can I solve a recurrence relation as the following: $x_{n+3} = x_{n+2} + x_{n+1} + x_{n} +n$ with $x_0=0$ and $x_1 = x_2 =1$?

Answer 1

Hint: as with any non-homogeneous linear equation, the general solution is a particular solution + the general solution of the homogeneous equation. So

1. Find a particular solution (try $x_n = a n + b$).
2. Find the general solution of the homogeneous equation.
3. Adjust the constants to match the initial conditions.

Note that (2) will involve the roots of the irreducible cubic $z^3 - z^2 - z - 1$, which are not very pleasant. So you won't get a "nice" closed-form solution.