# Find the generating function

I'm trying to find the generating function for this sequence:

$$0,0,3,0,9,17,33,65,129,257...$$

What I know so far:

$$0\cdot x^0 + 0\cdot x^1 + 3\cdot x^2 + 0 \cdot x^3$$

and

$$x^5(9+17x+33x^2+65x^3+129^4+257^5....$$

So what I have to do now Is just add the two, but I'm not 100% sure how to give a closed form answer for the second sequence. From what I can see it has an arithmetic progression of $8\cdot n$, so I've gotten this:

$$3x^2+x^5\sum_{n=1}^∞(9+8n)$$

What else do I need to do ? have I found the generating function?

## 1 Answer

The expression you are worried about can be rewritten as $$(1+x+x^2+x^3+x^4+\cdots)+(8+16x+32x^2+64x^3+\cdots).$$ Each is a geometric series, and you can write down the sum for each.

• I can see that you've separated the two sequences, but I'm not sure how. Could you explain? – Daniel Munoz Jun 5 '15 at 7:12
• Each of the numbers $9$, $17$, $33$, $65$, $129$, $257$ is one more than a power of two. – JimmyK4542 Jun 5 '15 at 7:13
• Is this before or after I take out the $x^5$? – Daniel Munoz Jun 5 '15 at 7:18
• I was looking only at the "series" part since the rest you know how to handle. The first series has sum $\frac{1}{1-x}$, the second has sum $\frac{8}{1-2x}$, so we get $\frac{x^5}{1-x}+\frac{8x^5}{1-2x}$. And of course there is the $3x^2$ in front that you know about. – André Nicolas Jun 5 '15 at 7:24
• I understand how to do that part, I'm just not sure how you were able to rewrite the series as you did in your answer. – Daniel Munoz Jun 5 '15 at 7:26