# Find a closed form for the generating function for this sequence

The sequence: $0, 0, 0, 1, 1, 1, 1, 1, 1, \ldots$ The book gives the answer of $\frac{x^3}{1-x}$ but I'm not sure how to get this answer. I understand the generating function of this sequence will be $0 + 0x + 0x^2 + 1x^3 + 1x^4+1x^5 + 1x^6 + \ldots$ But I'm not sure how to put this in the closed form.

• Yes, but what is the common ratio? x^3? Commented Jul 20, 2014 at 23:52
• You skipped the $x^4$ term, not sure if that's intentional or not. Commented Jul 20, 2014 at 23:53
• Another route is to start with the usual geometric series and subtract off the first three terms directly. Commented Jul 21, 2014 at 0:24

It's just an index shift.

Since

$${1\over 1-x}=\sum_{n=0}^\infty x^n$$

is generating for $1,1,1,\ldots$, and you want to make the first three into zeros, you multiply by $x^3$ resulting in an index shift:

$${x^3\over 1-x}=\sum_{n=0}^\infty x^{n+3}$$

So that you get the same sequence with three zeroes introduced at the beginning. If this is still not explicit enough, you can see this is:

$$\sum_{n=3}^\infty x^n$$

By making the index shift $n+3\mapsto n$.

• awesome, this makes sense now. I was missing understanding the index shift and translating the simple x^n to x^(n+3) Thank you so much for your quick response and thorough solution. Commented Jul 20, 2014 at 23:55
• @MannfromReno No problem. Be sure to accept the answer (and upvote if you're feeling nice!) so people know the question is closed. :-) Commented Jul 20, 2014 at 23:56
• Yup will do! just have to wait a few minutes until I'm allowed to accept it. Commented Jul 20, 2014 at 23:58

A more do-it-from-scratch approach:

Denote your sum $S$. Then $x \cdot S = x^4 + x^5 + \cdots$. Now subtracting $S-xS = x^3$. Solve for $S$, and you're done.

This is exactly the same method used to express a repeating decimal as a fraction, and a variation of it will work for finding the generating function for any repeating sequence.

• Thank you, I appreciate the alternative approach! Commented Jul 21, 2014 at 0:39