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

  • 1
    $\begingroup$ What is $\sum_{n\ge 1}(2x)^n$? $\endgroup$
    – wj32
    Mar 1 '13 at 8:08
  • $\begingroup$ Thanks @wj32. Where do I go from here? $\endgroup$
    – dsg
    Mar 1 '13 at 8:37
  • $\begingroup$ Is this homework, or are you just exploring? $\endgroup$
    – wj32
    Mar 1 '13 at 8:38
  • $\begingroup$ @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.) $\endgroup$
    – dsg
    Mar 1 '13 at 8:48
  • $\begingroup$ @dsg: I edited my answer $\endgroup$ 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}$$
Can you take it from here now?

  • $\begingroup$ 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. $\endgroup$
    – dsg
    Mar 1 '13 at 8:57
  • $\begingroup$ 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). $\endgroup$ Mar 1 '13 at 8:59
  • $\begingroup$ I must have made some mistake. I believe the answer should be $a_n = 2^{n+1} - 2$. $\endgroup$
    – dsg
    Mar 1 '13 at 9:03
  • $\begingroup$ @dsg: Another edit $\endgroup$ Mar 1 '13 at 9:10
  • $\begingroup$ I flipped a negative sign in the denominator. It is fixed now. Thanks so much for your help! $\endgroup$
    – dsg
    Mar 1 '13 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.