Using Generating Functions (again) to Solve Recurrences

Question

Consider the recursion $a_n = 2a_{n-1} + (-1)^n$ where $a_0 = 2$

Then $A(x) = \sum a_n x^n$ = $2 + \sum a_n x^n$ shifting the index of summation. The only next move I can think of is to now substitute $a_n = \sum (2a_{n-1} + (-1)^n)$ but I am not sure how this helps. Derivatives don't seem too helpful here either. Perhaps telescoping? Any ideas are appreciated.

Answer 1

You have $a_{n + 1} = 2 a_n - (-1)^n$, and thus: $$ \frac{A(z) - a_0}{z} = 2 A(z) - \frac{1}{1 + z} $$

Answer 2

You can also try to see the pattern:

$$a_1 = 2a_0 - 1\\ a_2 = 2\cdot 2 a_0 - 2 + 1\\ a_3 = 2\cdot 2\cdot 2a_0 - 2\cdot 2 + 2 - 1\\\vdots\\ a_n = 2^na_0 + (-1)^n\sum_{k=0}^{n-1}(-2)^k$$ The sum can of course be written in closed form.