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. 
 A: 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!
A: Hint.
Calling
$$
G(x) = \sum_{k=0}^{\infty}a_k x^k
$$
we have
$$
a_{k+1}x^k-2a_k x^k -(-1)^k x^k = 0
$$
or
$$
\frac 1x\sum_{k=1}^{\infty}a_k x^k - 2\sum_{k=0}^{\infty}a_k x^k-\sum_{k=0}^{\infty}(-1)^k x^k = 0
$$
now assuming $|x| < 1$ we have
$$
\frac 1x (G(x)-a_0)-2G(x)-\frac{1}{x+1}=0
$$
and
$$
G(x) = \frac{a_0}{1-2x}+\frac 13\frac{1}{1-2x}-\frac 13\frac{1}{1+x}
$$
etc.
