Coefficient of $x^k$ in polynomial

binomial-coefficientscombinatoricsmultinomial-coefficientspolynomials

Let $k, n, m \in \mathbb{N}, k \le n.$ Find the formula for coefficient of $x^k$ in $(x^n + x^{(n-1)} + … + x^2 + x + 1)^m$.

answer is in this question: faster-way-to-find-coefficient-of-xn-in-1-x-x2-x3-xak

But I still don't understand some parts of the answer.

So we can write the polynomial as:
$$
\left( \frac{1-x^{n+1}}{1-x} \right)^{m}
$$

$$
= (1-x^{n+1})^m \cdot (1-x)^{-m}
$$

All that I understand,
but now we write that as a sum:
$$
= \sum_{i=0}(-1)^i {m\choose i}x^{(n+1)i}\cdot\sum_{j=0} {j+m-1\choose j}x^j
$$

  1. both of the sums go up to $n$?
  2. What's the second sum?

And then finally we have the coefficient: $x^k$:
$$
\sum_{i=0}(-1)^i {m\choose i} {j+m-1\choose j}
$$
Where do we get $j$? Is one sum missing here?

I'm quite lost in both of the formulas with sums. Could you please point me in the right direction?

Also the OP mentions

I want to avoid iterating over N
to find the sum of products of certain coefficients, in the usual solution to this problem.

What's that usual solution?

Best Answer

Yes you are right that the summations are not properly indexed, so let's make the notations clear.

For $(1-x^{n+1})^m$, the power is a positive integer, so we can use the usual binomial theorem to get

$$(1-x^{n+1})^m=\sum_{i=0}^m(-1)^i{m\choose i}x^{(n+1)i}.$$

For $(1-x)^{-m}$, the power is a negative integer, so we use the negative binomial theorem to get

$$(1-x)^{-m}=\sum_{j=0}^\infty{m+j-1\choose j}x^j.$$

Note that the above sum is to $\infty$ and we need $|x|<1$. Now multiply these two sums, we have

$$\left(\frac{1-x^{n+1}}{1-x}\right)^m=\sum_{i=0}^m\sum_{j=0}^\infty(-1)^i{m\choose i}{m+j-1\choose j}x^{(n+1)i+j}.$$

Therefore, the coefficient for $x^k$ is given by

$$\sum_{\substack{0\leq i\leq m,\ j\geq0\\(n+1)i+j=k}}(-1)^i{m\choose i}{m+j-1\choose j}.$$

As for the usual solution mentioned by the OP, I believe it is to directly expand $(1+x+\cdots+x^n)^m$ using the usual binomial theorem, and then find the coefficient of $x^k$, but this could be tedious since we need to iterate over $n$. In comparison, the OP's method is to use the sum formula of geometric progressions $1+\cdots+x^n=(1-x^{n+1})/(1-x)$, so that we only have the product of two simple sums without needing to iterate over $n$.

Related Question