Find the coefficient of $x^n$ in the generating functions: $g(x) = \frac{x^3}{(1+x)^5 (1−x)^6}$

Question

One of the problems in my Discrete Math course states that we need to find the coefficient of $x^n$ in generating function $g(x) = \frac{x^3} {(1+x)^5 (1−x)^6}$

I separated $g(x) = \frac{x^3} {(1+x)^5 (1−x)^6}$ into $x^3$ * $\frac{1}{(1+x)^5}$ * $\frac{1}{(1-x)^6}$

Then got $f(x) = x^3 * \sum_{k=0}^\infty \binom{n+4}{4}(-1)^kx^k * \sum_{k=0}^\infty \binom{n+5}{5}x^k$

I dont know what to do from here, can you tell me what is the next step?

Answer 1

$$ \begin{align} \frac{x^3}{(1+x)^5 (1−x)^6} &=\frac{x^3+x^4}{\left(1-x^2\right)^6}\tag1\\ &=\left(x^3+x^4\right)\sum_{k=0}^\infty(-1)^k\binom{-6}{k}x^{2k}\tag2\\ &=\left(x^3+x^4\right)\sum_{k=0}^\infty\binom{k+5}{5}x^{2k}\tag3\\ &=\sum_{k=0}^\infty\binom{k+5}{5}\left(x^{2k+3}+x^{2k+4}\right)\tag4\\ &=\sum_{k=2}^\infty\binom{k+3}{5}\left(x^{2k-1}+x^{2k}\right)\tag5 \end{align} $$ Explanation:
$(1)$: multiply by $\frac{1+x}{1+x}$
$(2)$: use the series for $(1+x)^{-6}$
$(3)$: $\binom{-6}{k}=(-1)^k\binom{k+5}{5}$ when $k\ge0$
$\phantom{\text{(3):}}$ (negative binomial coefficients)
$(4)$: distribute the $x^3+x^4$
$(5)$: substitute $k\mapsto k-2$

Thus, if $n=2k-1$ or $n=2k$, then the coefficient of $x^n$ is $\binom{k+3}{5}$.

This can be stated as the coefficient of $x^n$ is $\binom{\left\lfloor\frac{n+7}2\right\rfloor}{5}$

Answer 2

The key is the generalized binomial theorem in the handy special case $(1-x)^{-s} =\sum_{k=0}^{\infty} \binom{s+k-1}{k}x^k =\sum_{k=0}^{\infty} \binom{s+k-1}{s-1}x^k $.

This implies that

$(1+x)^{-s} =\sum_{k=0}^{\infty} \binom{s+k-1}{k}(-1)^kx^k =\sum_{k=0}^{\infty} \binom{s+k-1}{s-1}(-1)^kx^k $

and, for any $m$,

$(1-x^m)^{-s} =\sum_{k=0}^{\infty} \binom{s+k-1}{k}x^{km} =\sum_{k=0}^{\infty} \binom{s+k-1}{s-1}x^{km} $.

For $m=2$ this is

$(1-x^2)^{-s} =\sum_{k=0}^{\infty} \binom{s+k-1}{k}x^{2k} =\sum_{k=0}^{\infty} \binom{s+k-1}{s-1}x^{2k} $.

Your problem is

$\begin{array}\\ g(x) &= \dfrac{x^3} {(1+x)^5 (1−x)^6}\\ &= \dfrac{x^3(1+x)} {(1+x)^6 (1−x)^6}\\ &= \dfrac{x^3(1+x)} {(1−x^2)^6}\\ &= \dfrac{x^3} {(1−x^2)^6}+\dfrac{x^4} {(1−x^2)^6}\\ \end{array} $

The results above should make this straightforward.

---

Actually, it's not that simple. Here's the rest.

$\begin{array}\\ \dfrac{x^3} {(1−x^2)^6} &=x^3\sum_{k=0}^{\infty} \binom{k+5}{5}x^{2k}\\ &=\sum_{k=0}^{\infty} \binom{k+5}{5}x^{2k+3}\\ &=\sum_{k=0}^{\infty} \binom{k+5}{5}x^{2(k+1)+1}\\ &=\sum_{k=1}^{\infty} \binom{k+4}{5}x^{2k+1}\\ \\ \dfrac{x^4} {(1−x^2)^6} &=x^4\sum_{k=0}^{\infty} \binom{k+5}{5}x^{2k}\\ &=\sum_{k=0}^{\infty} \binom{k+5}{5}x^{2k+4}\\ &=\sum_{k=0}^{\infty} \binom{k+5}{5}x^{2(k+2)}\\ &=\sum_{k=2}^{\infty} \binom{k+3}{5}x^{2k}\\ \end{array} $

This gives the coefficients of the even and odd terms.

To map these cases into a single one, use $h(k) =k-2\lfloor k/2 \rfloor $ where $h(k) = 0$ for even $k$ and $h(k) = 1$ for odd $k$.

Since we want even $k \to \lfloor k/2 \rfloor+3$ and odd $k \to \lfloor k/2 \rfloor+4$, we want

$\begin{array}\\ k &\to \lfloor k/2 \rfloor+3+h(k)\\ &\to \lfloor k/2 \rfloor+3+k-2\lfloor k/2 \rfloor\\ &\to k+3-\lfloor k/2 \rfloor\\ \end{array} $

Therefore $g(x) =\sum_{k=3}^{\infty} x^k\binom{k+3-\lfloor k/2 \rfloor}{5} $.

Answer 3

Here is a variation using the coefficient of operator $[x^n]$ which denotes the coefficient of $x^n$ of a series.

We start with $f(x)$ and obtain for $n\geq 3$: \begin{align*} \color{blue}{[x^n]f(x)}&=[x^n]x^3\sum_{k=0}^\infty\binom{k+4}{4}(-1)^kx^k\sum_{l=0}^\infty\binom{l+5}{5}x^l\tag{1}\\ &=[x^{n-3}]\sum_{k=0}^\infty\binom{k+4}{4}(-1)^kx^k\sum_{l=0}^\infty\binom{l+5}{5}x^l\tag{2}\\ &=\sum_{k=0}^{n-3}\binom{k+4}{4}(-1)^k[x^{n-3-k}]\sum_{l=0}^\infty\binom{l+5}{5}x^l\tag{3}\\ &=\sum_{k=0}^{n-3}\binom{k+4}{4}(-1)^k\sum_{l=0}^\infty\binom{l+5}{5}[x^{n-3-k}]x^l\\ &\,\,\color{blue}{=\sum_{k=0}^{n-3}\binom{k+4}{4}\binom{n-k+2}{5}(-1)^k}\tag{4} \end{align*}

Comment:

• In (1) we write the sums using different indices $k$ and $l$ which helps to not mix them up.

• In (2) we absorb $x^3$ by applying the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

• In (3) we use the linearity of the coefficient of operator and apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$ again. Note the upper index is set to $n-3$, since other indices do not contribute to the coefficient of $x^{n-3}$.

• In (4) we select the coefficient of $x^{n-3-k}$ which implies choosing $l=n-3-k$. Here we use $[x^p]x^q=\begin{cases}1&p=q\\0&p\ne q\end{cases}$.