I'm partial to solving with generating functions. Let

Multiply both sides of the recurrence by
and sum over all
.

Shift the indices and factor out powers of
as needed so that each series starts at the same index and power of
.

Now we can write each series in terms of the generating function
. Pull out the first few terms so that each series starts at the same index
.

Solve for
:

Splitting into partial fractions gives

which we can write as geometric series,


which tells us

# # #
Just to illustrate another method you could consider, you can write the second recurrence in matrix form as

By substitution, you can show that

or

Then solving the recurrence is a matter of diagonalizing the coefficient matrix, raising to the power of
, then multiplying by the column vector containing the initial values. The solution itself would be the entry in the first row of the resulting matrix.