How to express $(1+x+x^2+\cdots+x^m)^n$ as a power series?

Is it possible to express $(1+x+x^2+\cdots+x^m)^n$ as a power series?

Solution 1:

If you try to use the multinomial theorem, you get an $(m-1)$-fold iterated sum which might not be much progress. You can use inclusion-exclusion to express the coefficient of $x^k$ as a single sum instead.

The coefficient of $x^k$ in $(1+\ldots+x^m)^n$ is the number of ways to write $k$ as a sum of $n$ nonnegative integers such than none are at least $m+1$.

The number of ways to write $k$ as a sum of $n$ nonnegative integers is $k+n-1 \choose n-1$.

The number of ways to write $k$ as a sum of $n$ nonnegative integers so that a particular subset of size $s$ of the terms are at least $m+1$, with no restriction on the others, is the same as the number of ways to write $k-s(m+1)$ as a sum of $n$ nonnegative integers with no restrictions, $k-s(m+1)+n-1 \choose n-1$.

So, by inclusion-exclusion, the coefficient of $x^k$ in $(1+x+\ldots+x^m)^n$ is

$$\sum_{s=0}^{\lfloor k/(m+1) \rfloor} (-1)^s {n \choose s} {k-s(m+1)+n-1 \choose n-1}.$$

For example, the coefficient of $x^{50}$ in $(1+x+\ldots+x^{10})^{10}$ is $1018872811$ which is easy to compute with a single sum $(12565671261 - 16771066400 + 5598162900 - 374946000 + 1051050)$, but hard to compute with a $9$-fold sum over thousands of terms.

Another way to get the same answer is to expand $\left(\frac {1-x^{m+1}}{1-x}\right)^n$ as $(1-x^{m+1})^n \times (1-x)^{-n}$. Expand the first term with the binomial theorem, and then use $(1-x)^{-1} = 1 + x + x^2 + \ldots$ so $(1-x)^{-n} = \sum {n \choose k} x^k$, which is the binomial theorem with exponent $-n$. Then multiply the two single sums, isolating the coefficient of $x^k$.

Solution 2:

Yes, just multiply it out. Or treat $$\left( \frac{1-x^{m+1}}{1-x} \right)^n$$ as a generating function for the power series.

But I suspect your real question is whether there is a simple closed form for the coefficient of $x^k$ in the power series. Not for general $k$, $m$ and $n$, though there are formulae and descriptions: these are called multinomial coefficients (binomial if $m=1$, trinomial if $m=2$ etc.)