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