1

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?

Daniel Munoz
  • 63

1 Answers1

2

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.

André Nicolas
  • 507,029
  • I can see that you've separated the two sequences, but I'm not sure how. Could you explain? – Daniel Munoz Jun 05 '15 at 07:12
  • Each of the numbers $9$, $17$, $33$, $65$, $129$, $257$ is one more than a power of two. – JimmyK4542 Jun 05 '15 at 07:13
  • Is this before or after I take out the $x^5$? – Daniel Munoz Jun 05 '15 at 07: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 05 '15 at 07: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 05 '15 at 07:26
  • Pattern recognition. As explained by JimmyK4542, if you decrease each coefficient by $1$ you get consecutive powers of $2$, so it seemed reasonable to separate out the "nuisance" extra $1$'s. You can see my decomposed sum is the same as the one you had. Just add. – André Nicolas Jun 05 '15 at 07:30
  • Just noticed that – Daniel Munoz Jun 05 '15 at 07:34