Find a closed form for the generating function for this sequence

Question

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.

Answer 1

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

Answer 2

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.