Coefficient of $x^k$ in polynomial

Question

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?

Answer 1

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$.

Answer 2

Not sure whether I answer the OP question directly.

However under the condition $k \leq n$, I think there is a simple approach using stars and bars method.

Let us try to check the idea under a simple example first.

Question: Find the coefficient of $x^4$ in the expansion of $(1+x+x^2+x^3+x^4)^3$.

Note that $$(1+x+x^2+x^3+x^4)^3$$ $$=(1+x+x^2+x^3+x^4)(1+x+x^2+x^3+x^4)(1+x+x^2+x^3+x^4)$$

The coefficient of $x^4$ is obtained by counting the number of terms of the form $x^{r_1}x^{r_2}x^{r_3}$ where $r_1, r_2, r_3$ are non-negative integers such that $r_1+r_2+r_3=4$

This is equivalent to finding the number of solutions of $$r_1+r_2+r_3=4$$ where $r_1, r_2, r_3$ are non-negative integers.

By stars and bars method, the answer is $$\binom{4+3-1}{4}=15$$

Exactly the same reasonings apply to our question here.

Finding the coefficient of $x^k( k \leq n)$ in the expansion of $(1+x+x^2+x^3+ \cdots +x^n)^m$ is the same as finding the number of solutions of $$r_1+r_2+r_3+ \cdots + r_m=k$$ where $r_1, r_2, r_3, \cdots, r_m$ are non-negative integers.

Hence the answer is $$\binom{k+m-1}{k}.$$

(Note that the formula is correct only when $k \leq n.$)

Answer 3

In this approach, the denominator and numerator are processed in separate steps. It might help to better see what's going on. We use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. This way we can write for instance \begin{align*} [x^k](1+x)^n=\binom{n}{k} \end{align*}

We obtain \begin{align*} \color{blue}{[x^k]}&\color{blue}{\left(\frac{1-x^{n+1}}{1-x}\right)^{m}}\\ &=[x^k]\sum_{j=0}^{\infty}\binom{-m}{j}(-x)^j\left(1-x^{n+1}\right)^m\tag{1}\\ &=\sum_{j=0}^k\binom{m+j-1}{j}[x^{k-j}]\left(1-x^{n+1}\right)^m\tag{2}\\ &=\sum_{j=0}^k\binom{m+k-j-1}{k-j}[x^{j}]\sum_{l=0}^m\binom{m}{l}(-x)^{(n+1)l}\tag{3}\\ &=\sum_{j=0}^{\left\lfloor\frac{k}{n+1}\right\rfloor}\binom{m+k-(n+1)j-1}{k-(n+1)j} [x^{(n+1)j}]\sum_{l=0}^m\binom{m}{l}(-x)^{(n+1)l}\tag{4}\\ &\,\,\color{blue}{=\sum_{j=0}^{\left\lfloor\frac{k}{n+1}\right\rfloor}\binom{m+k-(n+1)j-1}{k-(n+1)j}\binom{m}{j}(-1)^j}\tag{5} \end{align*}

Comment:

• In (1) we expand the denominator using a binomial series expansion.

• In (2) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ and apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$. We also set the upper limit of the sum to $k$ since other summands do not contribute.

• In (3) we change the order of summation of the left sum $j\to k-j$ and expand the binomial. We see the power $j$ has to be an $(n+1)$-multiple of $l$.

• In (4) we take only $(n+1)$-multiples of $j$, since other summands do not contribute.

• In (5) we select the coefficient of $x^{(n+1)j}$ by taking $l=j$.

Answer 4

I would like to add that these numbers are called the Bi$^{s}$nomial coefficients $\binom{n}{k}_{s}$, where $$(1+x+x^{2}+\ldots+x^{s})^{n}=\sum\limits_{k\geq 0}^{n}\binom{n}{k}_{s}x^{k}. $$

See Table 1 in this paper for more notations and names of these numbers.