Here's one way of solving via the generating function method.
For the sequence
, denote its generating function by
with
In the recurrence relation, multiply all terms by
and sum over all non-negative integers larger than 2:
The goal is to rewrite everything we can in terms of
and (possibly) its derivatives. For example, the term on the LHS can be rewritten by adding and subtracting the the first three terms of
:
For the other terms on the RHS, you need to do some re-indexing of the sum:
So in terms of the generating function, the recurrence can be expressed as
Decomposing into partial fractions, we get
and we recognize that for appropriate values of
, we can write these as geometric power series:
Or, more compactly,
which suggests that the solution to the recurrence is