# Generating functions for sum of powers of two

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}$

-
What is $\sum_{n\ge 1}(2x)^n$? – wj32 Mar 1 '13 at 8:08
Thanks @wj32. Where do I go from here? – dsg Mar 1 '13 at 8:37
Is this homework, or are you just exploring? – wj32 Mar 1 '13 at 8:38
@wj32 -- I'm trying to learn independently. I'm currently following along in the Analytic Combinatorics class on Coursera, but this is a sequence that I ran into on my own. (Incidentally, this sequence is the expected number of coin flips you need before you get $n$ heads in a row.) – dsg Mar 1 '13 at 8:48
@dsg: I edited my answer – Dennis Gulko Mar 1 '13 at 8:49

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}$$
I have $A(x) = \frac{1}{2x - 1} - \frac{4}{x - 1} - 3$. So I can write it as $A(x) = -3 + \sum (4 - 2^n) x^n$. This is actually the first problem in generating functions I'm doing on my own. I'm not sure where to go from here. – dsg Mar 1 '13 at 8:57
Now your'e done - by comparing coefficients with $A(x)=\sum_{n=1}^\infty a_nx^n$, you have a closed form for $a_n$ (assuming there are no computation mistakes - but here you clearly have at least one, since you get $a_n=4-2^n$, which is negative for $n>2$, while $a_n$ is positive). – Dennis Gulko Mar 1 '13 at 8:59
I must have made some mistake. I believe the answer should be $a_n = 2^{n+1} - 2$. – dsg Mar 1 '13 at 9:03