Find the coefficient of $x^n$ in the generating functions: $g(x) = \frac{x^3}{(1+x)^5 (1−x)^6}$ 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?
 A: $$
\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}$
A: 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}
$.
A: 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}$.
