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 $$
- both of the sums go up to $n$?
- 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?