 Solution

Substitution of $y_n=r^n$ gives the characteristic equation of a linear recurrenceThe repeated characteristic root of a linear recurrence $1$ supplies the solutions $1$ and $n$, while the simple root $-2$ supplies $(-2{)}^n$. They are linearly independent: their values at three consecutive indices have nonzero determinant. A third-order linear recurrence relation is uniquely determined by three consecutive initial values, so these three solutions span its solution space. The general solution is