Recursion Question using Generating Functions Here is my question:
Consider the recurrence,
$$a_{n+1}=2a_n+(-1)^n$$
with initial condition,
$$a_0=0$$
Find and prove a formula for $a_n$.
I don't really know how to prove this formula
I tried going with a generating function method, but that kind of led nowhere. 

The sequence generated by the recurrence relation is;
$$0, 1, 1, 3, 5, 11, 21, \dots$$
Write the recurrence relation as;
$$a_n-2a_{n-1}=(-1)(-1)^n$$
Get the generating function, $GF$ in the standard way;
$$GF=0+x+x^2+3x^3+5x^4+11x^5+21x^6+\dots$$
$$-2xGF=0+0x-2x^2-2x^3-6x^4-10x^5-22x^6+\dots$$
$$(1-2x)GF=0+x-x^2+x^3-x^4+x^5-x^6+x^7-x^8+ \dots$$
$$(1-2x)GF=-\big(\frac{1}{1+x}\big)+1$$
$$GF=\frac{x}{(1-2x)(1+x)}$$
Use partial fractions to get;
$$GF=\frac{1}{3}\times \frac{1}{1-2x}-\frac{1}{3}\times \frac{1}{1+x}$$
These are standard bits that translate directly into the formula;
$$a_n=\frac{1}{3}2^n-\frac{1}{3}(-1)^n$$
or
$$a_n=\frac{2^n-(-1)^n}{3}$$
Check this gives the sequence expected, which it does!
