1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I can see that you've separated the two sequences, but I'm not sure how. Could you explain? $\endgroup$ – Daniel Munoz Jun 5 '15 at 7:12
  • $\begingroup$ Each of the numbers $9$, $17$, $33$, $65$, $129$, $257$ is one more than a power of two. $\endgroup$ – JimmyK4542 Jun 5 '15 at 7:13
  • $\begingroup$ Is this before or after I take out the $x^5$? $\endgroup$ – Daniel Munoz Jun 5 '15 at 7:18
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Jun 5 '15 at 7:24
  • $\begingroup$ 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. $\endgroup$ – Daniel Munoz Jun 5 '15 at 7:26

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.