Find the sequence given its generating function.

Question

$$\frac{1 + x + x^2}{(1-x)^2}$$ Hint is to do this using multiplication. $1 + x + x^2$ is sequence $(1,1,1,0,0,...)$ and $\frac{1}{(1-x)^2}$ is $(1,2,3,4,....)$, but I don't know what to do next.

Answer 1

You probably know that $\frac{1}{1-x}=1+x+x^2+\dots$. If not, observe that $$(1-x)(1+x+x^2+\dots)=(1+x+x^2+\dots)-(x+x^2+x^3+\dots)=1$$ Then $$\frac{1}{(1-x)^2}=\left(\frac{1}{1-x}\right)'=1+2x+3x^2+4x^3+\dots$$

Now, $1+x+x^2=(1-x)^2+3x$. Or you can just divide $x^2+x+1$ by $(1-x)^2$. The important thing is to obtain that the quotient is $1$ and the remainder is $3x$. So, $$\begin{align}\frac{1+x+x^2}{(1-x)^2}&=1+\frac{3x}{(1-x)^2}\\&=1+3x(1+2x+3x^2+4x^3+\dots)\\&=1+3x+3\cdot2x^2+3\cdot 3x^3+3\cdot 4x^4+3\cdot 5x^5+\dots\end{align}$$

Answer 2

You know $\dfrac1{(1-x)^2}=1+2x+3x^2+4x^3+\cdots.$

Therefore, $\dfrac x{(1-x)^2}=x(1+2x+3x^2+4x^3+\cdots)=x+2x^2+3x^3+\cdots$

and $\dfrac {x^2}{(1-x)^2}=x^2(1+2x+3x^2+4x^3+\cdots)=x^2+2x^3+\cdots.$

Therefore, adding these up,

$\dfrac {1+x+x^2}{(1-x)^2}=1+(2+1)x+(3+2+1)x^2+(4+3+2)x^3+\cdots$

$=1+3x+6x^2+9x^3+\cdots$.