Prove, that generating function for $0,0,0,0,0,0,0,3,1,3,1,...$ is $\frac{x^7}{1-x} + \frac{2x^7}{1-x^2}$

Question

Prove, that generating function for $0,0,0,0,0,0,0,3,1,3,1,...$ is $$\frac{x^7}{1-x} + \frac{2x^7}{1-x^2}$$ I have a really problem with understanding generating function, so I don't show my attempt so I am asking for advice. Thanks in advance.

Answer 1

To say that $g(x)$ is the (ordinary) generating function of a sequence $\langle a_n:n\in\Bbb N\rangle$ is to say that

$$g(x)=\sum_{n\ge 0}a_nx^n\;.$$

Let’s look at an example using some of the ideas that you need for your problem. Suppose that we want the generating function of the sequence

$$\langle 0,0,0,0,0,4,0,0,4,0,0,4,0,0,4,\ldots\rangle\;;\tag{0}$$

this sequence starts with $5$ zeros and then repeats the terms $4,0,0$ forever. Forget that first bit: the basic structure is $\langle 4,0,0,4,0,0,4,0,0,\ldots\rangle$. Any regular cycling like this is easy to generate. The simplest example is

$$\frac1{1-x}=\sum_{n\ge 0}x^n\;,\tag{1}$$

from the formula for the sum of a geometric series; the coefficient of $x^n$ is $1$ for each $n\ge 0$, so $(1)$ is the generating function and power series for the sequence $\langle 1,1,1,1,\ldots\rangle$. I don’t want ones for my non-zero terms, though: I want fours. That’s easily arranged: multiply $(1)$ by $4$ to get

$$\frac4{1-x}=4\sum_{n\ge 0}x^n=\sum_{n\ge 0}4x^n\;,\tag{2}$$

corresponding to the sequence $\langle 4,4,4,4,\ldots\rangle$ of coefficients.

Of course I also want the fours to occur only every third term, not every term. This is almost as easy to arrange, still using the formula for the sum of a geometric series. The trick is to replace the ratio $x$ in the geometric series by $x^3$, so that $(1)$ becomes

$$\frac1{1-x^3}=\sum_{n\ge 0}(x^3)^n=\sum_{n\ge 0}x^{3n}\;,$$

with coefficient sequence $\langle 1,0,0,1,0,0,1,0,0,\ldots\rangle$, and $(2)$ becomes

$$\begin{align*} \frac4{1-x^3}&=4\sum_{n\ge 0}(x^3)^n=\sum_{n\ge 0}4x^{3n}\\\\ &=4x^0+0x^1+0x^2+4x^3+0x^4+0x^5+4x^6+0x^7+0x^8+\ldots\;, \end{align*}\tag{3}$$

with coefficient sequence $\langle 4,0,0,4,0,0,4,0,0,\ldots\rangle$.

Now all we need is to push $5$ zeros in front of this sequence of coefficients. In other words, instead of having

$$4x^0+0x^1+0x^2+4x^3+0x^4+0x^5+4x^6+0x^7+0x^8+\ldots\;,$$

we want to start with the five zero terms

$$0x^0+0x^1+0x^2+0x^3+0x^4$$

and then have the coefficients cycling $4,0,0,4,0,0,\ldots$:

$$0x^0+0x^1+0x^2+0x^3+0x^4+\color{blue}{4x^5+0x^6+0x^7+4x^8+0x^9+0x^{10}+\ldots}\;.$$

Notice that the cycling part, in blue, is just $x^5$ times the series in $(3)$: multiplying by $x^5$ pushes all of the coefficients $5$ terms to the right, and of course the $5$ new low-order terms are all $0$. Thus, the generating function of the sequence $(0)$ is

$$\frac{4x^5}{1-x^3}\;.$$

Your problem is both easier and harder. It’s easier, because you already have the generating function and merely have to explain why it generates the given sequence of coefficients. It’s a little harder, because you have to see how the two summations combine. If you’re having trouble, I would start by seeing what sequences correspond to the functions

$$\frac1{1-x}\quad\text{and}\quad\frac2{1-x^2}\;:$$

turn those fractions into power series using the ideas above, write out the first several terms of each, and see what pattern of coefficients you get — i.e., what sequences these functions generate. Then add the sequences term by term to see what

$$\frac1{1-x}+\frac2{1-x^2}$$

generates. Finally, see what effect the multiplication by $x^7$ has.

Answer 2

Hint:$$\frac{x^7}{1-x} + \frac{2x^7}{1-x^2} \\=x^7\left( \frac1{1-x}+\frac2{1-x^2}\right) \\=x^7\left(\sum_{k=0}^\infty x^k+2\sum_{k=0}^\infty x^{2k}\right)$$

Answer 3

Hint. Try to use that $$ \frac{1}{1-x^n} = 1 + x^n + x^{2n} + \dots $$