Identify the solution to an = 2an − 1 + an − 2 − 2an − 3 for n = 3, 4, 5, . . , with a0 = 3, a1 = 6, and a2 = 0.

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

Ithink the answer is d.