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.