Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
show 1 more comment

1 Answer

up vote 1 down vote accepted

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?

share|improve this answer
    
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
    
@dsg: Another edit –  Dennis Gulko Mar 1 '13 at 9:10
    
I flipped a negative sign in the denominator. It is fixed now. Thanks so much for your help! –  dsg Mar 1 '13 at 9:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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