Partial Fraction of $\frac{1-x^{11}}{(1-x)^4} $ for Generating Function

Question

The original question involves using generating functions to solve for the number of integer solutions to the equation $c_1+c_2+c_3+c_4 = 20$ when $-3 \leq c_1, -3 \leq c_2, -5 \leq c_3 \leq 5, 0 \leq c_4$.

Using generating functions I was able to get it into the rational polynomial form: $$f(x) = {\left(\frac{1}{1-x}\right)}^3\left(\frac{1-x^{11}}{1-x}\right) = \frac{1-x^{11}}{{(1-x)}^4}$$

I was also able to determine that the sequence could be represented in two factors: $${\left(1+x^1+x^2+x^3+\cdots\right)}^3\left(1+x^1+x^2+\cdots+x^{10}\right)$$

However, to find the coefficient on $x^{31}$ to solve the problem, I figured I would have to get the term $\frac{1-x^{11}}{{(1-x)}^4}$ into a more typical generating function summation form. Thus, I endeavored to find the partial fraction decomposition of the term, however, I can't seem to do it at all.

How would I find the partial fraction decomposition of $\frac{1-x^{11}}{{(1-x)}^4}$? Or is there a better method in using ${(1+x^1+x^2+x^3+\ldots)}^3(1+x^1+x^2+\ldots+x^{10})$ in order to find the coefficient on $x^{31}$?

Thank you very much for your help, I've been trying this partial fraction for a while now and Wolfram alpha doesn't seem to be giving me an answer that is of much value.

Answer 1

$$\begin{align} \frac{1-x^{11}}{(1-x)^4}&=(1-x^{11})\sum_{n\ge0}\frac{(n+1)(n+2)(n+3)}{6}x^n\\ &=\sum_{n\ge0}\frac{(n+1)(n+2)(n+3)}{6}x^n-\sum_{n\ge0}\frac{(n+1)(n+2)(n+3)}{6}x^{n+11}\\ &=\sum_{n\ge0}\frac{(n+1)(n+2)(n+3)}{6}x^n-\sum_{n\ge11}\frac{(n-10)(n-9)(n-8)}{6}x^{n}\\ &=\sum_{n\ge0}\frac{1}{6}\bigg((n+1)(n+2)(n+3)-(n-10)(n-9)(n-8)[n\ge11]\bigg)x^n, \end{align}$$ where $[n\ge11]$ is the Iverson Bracket.

Answer 2

I would use the generalized binomial theorem in the form

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

Then

$\begin{array}\\ \dfrac{1-x^a}{(1-x)^s} &=\sum_{k=0}^{\infty} \binom{s+k-1}{s-1}x^k -x^a\sum_{k=0}^{\infty} \binom{s+k-1}{s-1}x^k\\ &=\sum_{k=0}^{\infty} \binom{s+k-1}{s-1}x^k -\sum_{k=0}^{\infty} \binom{s+k-1}{s-1}x^{k+a}\\ &=\sum_{k=0}^{\infty} \binom{s+k-1}{s-1}x^k -\sum_{k=a}^{\infty} \binom{s+k-a-1}{s-1}x^{k}\\ &=\sum_{k=0}^{a-1} \binom{s+k-1}{s-1}x^k +\sum_{k=a}^{\infty} \binom{s+k-1}{s-1}x^k -\sum_{k=a}^{\infty} \binom{s+k-a-1}{s-1}x^{k}\\ &=\sum_{k=0}^{a-1} \binom{s+k-1}{s-1}x^k +\sum_{k=a}^{\infty} \left(\binom{s+k-1}{s-1}-\binom{s+k-a-1}{s-1}\right)x^k \\ &=\sum_{k=0}^{a-1} \binom{s+k-1}{s-1}x^k +\sum_{k=a}^{\infty} \left(\dfrac{(s+k-1)!}{(s-1)!k!}-\dfrac{(s+k-a-1)!}{(s-1)!(k-a)!}\right)x^k \\ &=\sum_{k=0}^{a-1} \binom{s+k-1}{s-1}x^k +\sum_{k=a}^{\infty} \left(\dfrac{(s+k-1)!}{(s-1)!k!}-\dfrac{(s+k-a-1)!}{(s-1)!(k-a)!}\right)x^k \\ \end{array} $

You can do more manipulation if you want.

Answer 3

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

We obtain \begin{align*} \color{blue}{[x^{31}]\frac{1-x^{11}}{(1-x)^4}} &=\left([x^{31}]-[x^{20}]\right)\sum_{j=0}^{\infty}\binom{-4}{j}(-x)^j\tag{1}\\ &=\left([x^{31}]-[x^{20}]\right)\sum_{j=0}^{\infty}\binom{j+3}{j}x^j\tag{2}\\ &=\binom{34}{31}-\binom{23}{20}\tag{3}\\ &\,\,\color{blue}{=4\,213} \end{align*}

Comment:

• In (1) we use the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$ and make a binomial series expansion.

• In (2) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (3) we select the coefficients accordingly.