# Find the sequence given its generating function

I have a generating function of some real-value sequence given by: $$f(x) = \frac{(1+x)^2}{(1-x)^4}$$ I need to find the sequence this function generates.
This problem seems to be tricky - to get the denominator part, it looks as if it required differentiation - I could get the expression for $$\frac{1}{1-x}$$ and differentiate twice - but then the numerator part would spoil everything as it would not fit.

How should I attempt this?

• Differentiating $1/(1-x)$ (thrice) looks like a good start. What do you get, and why does it “spoil everything” and does “not fit”? – Martin R May 6 '18 at 15:01
• You can directly compute the coefficient of $x^{n-2}$ in $\frac{1}{(1-x)^4}$. This will be the number of solutions of $x_1+x_2+x_3+x_4=n-2$. – justanothermathstudent May 6 '18 at 15:03
• I get $$\frac{1}{(1-x)^4} = \sum \frac{1}{6} n (n-1) (n-2) x^{n-3}$$ Now, if I were to multiply both sides by $(1+x)^2$, it would not work – Aemilius May 6 '18 at 15:10

It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.

We obtain for $n\geq 0$: \begin{align*} \color{blue}{[x^n]f(x)}&=[x^n]\frac{(1+x)^2}{(1-x)^4}\\ &=[x^n](1+x)^2\sum_{j=0}^\infty\binom{-4}{j}(-x)^j\tag{1}\\ &=\left([x^n]+2[x^{n-1}]+[x^{n-2}]\right)\sum_{j=0}^\infty\binom{j+3}{3}x^j\tag{2}\\ &\,\,\color{blue}{=\binom{n+3}{3}+2\binom{n+2}{3}+\binom{n+1}{3}}\tag{3} \end{align*}

Comment:

• In (1) we use the binomial series expansion.

• In (2) we use the linearity of the coefficient of operator, apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$ and use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (3) we select the coefficients accordingly.

From (3) we obtain the representation \begin{align*} \color{blue}{f(x)}&=\sum_{n=0}^\infty\left[\binom{n+3}{3}+2\binom{n+2}{3}+\binom{n+1}{3}\right]x^n\\ &\,\,\color{blue}{=1+6x+19x^2+44x^3+85x^4+146x^5+\cdots} \end{align*}

Let $k\geq 1$. Note that $$(1+x+x^2+\dotsb)^{k}=(1-x)^{-k}=\sum_{n=0}^\infty\left(\!\!{k\choose n}\!\!\right)x^n=\sum_{n=0}^\infty\binom{n+k-1}{k-1}x^n$$ where $\left(\!\!{k\choose n}\!\!\right)=\#\{(x_1,\dotsc,x_k),\, x_i\geq0, \,x_i\in\mathbb{Z}\mid x_1+\dotsb+ x_k=n\}=\binom{n+k-1}{k-1}$ by a stars and bars argument and multiplying out. Thus $$(1-x)^{-4}=\sum_{n=0}^\infty\binom{n+3}{3}x^n$$

For notation, let $[x^n]A(x)$ extract the coefficient of $x^n$ in the generating function $A(x)$ and observe that $[x^n](x^kA(x))=[x^{n-k}]A(x)$. Thus \begin{align} [x^n]\left((1+x)^2(1-x)^{-4}\right)&= [x^n]\left(\frac{1}{(1-x)^{4}}+\frac{2x}{(1-x)^{4}}+\frac{x^2}{(1-x)^{4}}\right)\\ &=\binom{n+3}{3}+2\binom{n+2}{3}+\binom{n+1}{3} \end{align} Techinally for the last two binomials on the previous line we should add the proviso that $n\geq 1$ and $n\ge 2$ but since both expressions vanish even when this is not the case we are fine.