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?

  • $\begingroup$ Differentiating $1/(1-x)$ (thrice) looks like a good start. What do you get, and why does it “spoil everything” and does “not fit”? $\endgroup$ – Martin R May 6 '18 at 15:01
  • $\begingroup$ 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$. $\endgroup$ – justanothermathstudent May 6 '18 at 15:03
  • $\begingroup$ 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 $\endgroup$ – 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*}


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.