I have the recurrence:
$a_1 = 2$
$a_{n+1} = 2^n + a_n$
How can I use generating functions to compute a closed form for $a_n$?
Here is what I did on my own:
Let $A(x) = \sum_{n \geq 1} a_n x^n$
Multiply by $x^n$ and sum over valid values of $n$:
$\sum_{n \geq 1} a_{n+1} x^n = \sum_{n \geq 1} (2^n + a_n) x^n$
On the left we have:
$\sum_{n \geq 1} a_{n + 1} x^n = a_2 x + a_3 x^2 + a_4 x^4 + \ldots = A(x)/x - a_1$
On the right we have:
$\sum_{n \geq 1} (2^n + a_n) x^n = \sum_{n \geq 1} 2^n x^n + A(x)$
So with some algebra (and the fact that $a_1 = 2$):
$A(x) = \frac{x}{1- x} (\sum_{n \geq 1} 2^n x^n + 2)$
This is where I get stuck. Did I make a mistake? Am I going about this the wrong way?
EDIT: Thanks to hints from @wj32 and @Dennis Gulko:
$\sum_{n \geq 1} 2^n x^n = \sum_{n \geq 1} (2x)^n = \frac{2x}{1 - 2x} $
Using this identity and some algebra, I get:
$A(x) = \frac{x}{1-x} \cdot \frac{2 - 2x}{1 - 2x} = \frac{2x}{1 - 2x}$
If $A(x)=\sum_{n=1}^\infty a_nx^n$, then $$\begin{align*}\frac{A(x)}{x}&=\sum_{n=1}^\infty a_nx^{n-1}=\sum_{n=0}^\infty a_{n+1}x^n=a_1+\sum_{n=1}^\infty a_{n+1}x^n=a_1+\sum_{n=1}^\infty \left(2^n+a_n\right)x^n\\ &=a_1+\sum_{n=1}^\infty \left(2x\right)^n+\sum_{n=1}^\infty a_nx^n=a_1+\left(\frac{1}{1-2x}-1\right)+A(x) \end{align*}$$ Edit: Using some algebra you should get: $$A(x)=\frac{2-2x}{1-2x}\cdot\frac{x}{1-x}=\frac{2x}{1-2x}$$
Can you take it from here now?