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

  • 5
    $\begingroup$ Maybe you should replace "Is it possible to" with "Can you help me to"? $\endgroup$ – AD. Mar 24 '11 at 12:08
  • 7
    $\begingroup$ I guess Leonhard Euler solved your problem some time ago. Take a look at arxiv.org/abs/math.HO/0505425. $\endgroup$ – Fabian Mar 24 '11 at 15:56

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


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

  • 6
    $\begingroup$ Those are not multinomial coefficients. $\endgroup$ – Douglas Zare Mar 24 '11 at 19:41

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)

decomposition of coefficients of power of formal powerseries


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.

  • $\begingroup$ The multinomial theorem will still leave the coefficients as an iterated sum. $\endgroup$ – Douglas Zare Mar 24 '11 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.