Is there any general way to find coefficient of $x^i$ in $(x+x^2+…+x^k)^n$
It is easy to solve when k is small like $k=3$ or $k=4$ by using multinomial coefficient
But how can we solve a problem: find coefficient of $x^{50}$ in the expansion of $(x+x^2+…+x^{20})^{10}$
Any help would be appreciated.
Best Answer
Hint: Write the polynomial as $$ x^n\cdot (1-x^{k})^n\cdot (1-x)^{-n}\tag 1 $$ then take the convolution of the generating functions for the last two factors: \begin{align} (1-x^k)^n&=\sum_{j=0}^n \binom{n}j(-1)^j x^{kj},\\ (1-x)^{-n}&=\sum_{j=0}^\infty \binom{-n}j(-1)^j x^j=\sum_{j=0}^\infty \binom{n+j-1}{n-1} x^j\tag 2 \end{align} You want the coefficient of $x^i$ in $(1)$, which is the same as the coefficient of $x^{i-n}$ in the product of the series in $(2)$.
Edit: To explain the part about $\binom{-n}j$. Note that when $n$ is positive, we have the usual formula $$ \binom{n}k=\frac{n(n-1)\dots (n-k+1)}{k!} $$ What is nice about the expression on the right is that it makes sense for negative (or even complex) $n$. When you substitute a negative value for $n$, you get \begin{align} \binom{-n}{k} &=\frac{(-n)(-n-1)\cdots (-n-k+1)}{k!} \\&=(-1)^k\frac{n(n+1)\cdots (n+k-1)}{k!} \\&=(-1)^k\binom{n+k-1}{k} \end{align} Furthermore, this natural generalization also agrees nicely with the binomial theorem. With this definition, it turns out that the Taylor series expansion $$ (1+x)^n=\sum_{k=0}^\infty \binom{n}k x^k $$ holds when $n$ is negative, or even complex. These two points justify $(2)$.