Generating function, finding coefficient (decomposing)

Question

I just started learning about generating functions, and there is a problem that I have the solution to, but I'm wondering if there is a better general method to solve problems of that kind.

If I want to find the coefficient of $x^8$ in

$$\left( 1+x+x^2+x^3+x^4 \right) \sum_{k=0}^{\infty} (-1)^k {-2 \choose k} x^k, $$

is there a better method than to decompose it as

$${-2\choose 8}-{-2\choose 7}+{-2\choose 6}-{-2\choose5}+{-2\choose4}$$

$$={9\choose8}+{8\choose7}+{7\choose6}+{6\choose5}+{5\choose4}$$

$=35$?

It is the suggested method in the literature, but it seems to me there should be a better way, since this method would take a lot of time if the coefficient was, for example, the coefficient of $x^{20}$ or larger.

Edit

I found a somewhat similar thread here, and tried to apply that method, but that gives me the wrong answer. That method dealt with partitions, so that in my case the term $x^8$ can arise from $x^4 \cdot p(4,2)x^4, x^3 \cdot p(5,2)x^5, x^2 \cdot p(6,2)x^6, x \cdot p(7,2)x^7$ and $1\cdot p(8,2)x^8.$

Counting all such partitions gives me the answer 25, where it should be 35...

Answer 1

There is no essentially different method available. However there are some techniques, which could help to perform such calculations.

Note, that the calculcation of $x^8$ and of $x^{20}$ is not essentially different, since it is the polynomial \begin{align*} 1+x+x^2+x^3+x^4 \end{align*} which determines in both cases $5$ summands, which are to add. So, if this polynomial has more than $5$ summands, this could make the calculation somewhat more tedious.

In fact, if we use summation with the sigma notation this can also mitigate the complexity of calculations.

It is also convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. We can write e.g. $$[x^8]\sum_{k=0}^{\infty} (-1)^k {-2 \choose k} x^k=(-1)^8\binom{-2}{8}$$.

We obtain \begin{align*} [x^8]&\sum_{j=0}^4x^j\sum_{k=0}^{\infty} (-1)^k {-2 \choose k} x^k\\ &=\sum_{j=0}^4[x^{8-j}]\sum_{k=0}^{\infty} (-1)^k {-2 \choose k} x^k\tag{1}\\ &=\sum_{j=0}^4 (-1)^{8-j} {-2 \choose 8-j}\tag{2}\\ &=\sum_{j=0}^4 {9-j \choose 8-j}\\ &=\sum_{j=0}^4 (9-j)=9\sum_{j=0}^41-\sum_{j=0}^4j=9\cdot5-\frac{4\cdot 5}{2}\tag{3}\\ &=35 \end{align*}

Comment:

• In (1) we use the rule $[x^n]x^k=[x^{n-k}]$ together with the linearity of the coefficient of operator

• In (2) we select the coeffient of $x^{j-8}$ of the series $\sum_{k=0}^{\infty} (-1)^k {-2 \choose k} x^k$

• In (3) we use the formula for the finite geometric series $\sum_{j=0}^{n}j=\frac{n(n+1)}{2}$

Note: This kind of calculation may look somewhat more complicated, but it is independent of the coefficient $[x^k]$ and due to the sigma notation and usage of the finite geometric series it is independent of the number of summands of the polynomial.