How to extract coefficients of a generating function like this one, using a computer?

Question

For example if we have the generating function $G (x) = (1 + x + ... + x^k)^{10}$ and we want to calculate the coefficient of $x^{3k}$: What is the best way to go about it using Matlab or Mathematica?

Answer 1

You can write: $\begin{align*} (1 + z + \dotsb + z^k)^{10} &= \left( \frac{1 - z^{k + 1}}{1 - z} \right)^{10} \\ &= (1 - z^{k + 1})^{10} \cdot (1 - z)^{-10} \\ &= \left( \sum_{0 \le r \le 10} (-1)^r \binom{10}{r} z^r \right) \cdot \left( \sum_{s \ge 0} (-1)^s \binom{-10}{s} z^{k s} \right) \\ &= \left( \sum_{0 \le r \le 10} (-1)^r \binom{10}{r} z^r \right) \cdot \left( \sum_{s \ge 0} \binom{10 + s - 1}{s - 1} z^{k s} \right) \\ &= \sum_{r, s \ge 0} (-1)^r \binom{10}{r} \binom{10 + s - 1}{s - 1} z^{r + k s} \end{align*}$

From this you wan to pick off coefficients such that $r + s k = 3 k$. This means $r = 0, s = 3$, $r = k, s = 2$, $r = 2 k, s = 1$ or $r = 3 k, s = 0$.