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

Question

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

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

Answer 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.)

Answer 3

Here is a decomposition of the coefficients which I've worked out recently and have not seen elsewhere. It describes the coefficients of the general function $$f(x)= 1 + ax + bx^2+cx^3+dx^4+\ldots...$$ and its powers.
See the scan of the table for the decomposition below.(I've posted this in another stackexchange-question recently)

If all $a=b=c=d=\ldots=1 $ then the compositions reduces to simple binomials.
This decomposition can also be used to find the formal powerseries for the iteration of $f(x)$

Here the k'th coefficient at $x^k$ of the $p$'th power $f(x)^p=(1+x+x^2+x^3+...)^p $ is $$ f_{k,p} = \sum_{j=0}^{k-1} \left({\tbinom {k-1}{j} \over (1+j)! } \prod_{m=0}^j(p-m) \right) $$

[update] Reworking that decomposition allows a much simpler formula. Combining the terms appropriately gives for the $k$'th coefficient of $$f(x)^p = (1+x+x^2+x^3+...)^p = 1+c_1 ~ x+ c_2~x^2 + c_3 ~ x^3 + ... $$ $$ c_k = \sum_{j=1}^k \binom{p}{j}\binom{k-1}{j-1} $$ (this much shorter solution was already hinted in some earlier answers/comments, sorry I didn't catch that earlier)

Answer 4

This is a polynomial, so it's trivially a power series. If you want to expand it you can for example use the multinomial theorem: http://en.wikipedia.org/wiki/Multinomial_theorem.