How to find the closed form for this polynomial generating function with 2 variables

Question

I have the following generating function:

$ (x + x^2 + x^3 + ... + x^m)^k $

I want to find the coefficient of $x^n$ ($ n \geq k,m $)

I tried to think of it from a combinatorial perspective but couldn't get anywhere.

How do I go about it? Any ideas would be appreciated..

EDIT: As Macavity has pointed out, that is indeed what I'm trying to find.

The recurrence I came up with is:

$$ f(n,k) = \sum_{i=1}^m f(n-i, k-1) $$ where $ f(n,k) = 0 \space if \space n \leq 0 $ or $k \leq 0$

$and \space f(n,1) = 1 \space if n \in [1,m]$

Answer 1

It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a series.

We obtain for $n,k\geq 1$ \begin{align*} \color{blue}{[x^n]}&\color{blue}{(x+x^2+\cdots+x^m)^k}\\ &=[x^n]x^k(1+x+\cdots+x^{m-1})^k\tag{1}\\ &=[x^{n-k}]\left(\frac{1-x^m}{1-x}\right)^k\tag{2}\\ &=[x^{n-k}]\sum_{l=0}^k\binom{k}{l}(-1)^lx^{ml}\sum_{j=0}^\infty\binom{-k}{j}(-x)^j\tag{3}\\ &=\sum_{l=0}^{\min\{\lfloor k/m \rfloor, \lfloor (n-k)/m \rfloor\}}\binom{k}{l}(-1)^l[x^{n-k-ml}]\sum_{j=0}^\infty\binom{k+j-1}{j}x^j\tag{4}\\ &\color{blue}{=\sum_{l=0}^{\min\{\lfloor k/m \rfloor, \lfloor (n-k)/m \rfloor\}}(-1)^l\binom{k}{l}\binom{n-ml-1}{k-1}}\tag{5} \end{align*}

Comment:

• In (1) we factor out $x^k$.

• In (2) we use the geometric series expansion and we apply the rule $$[x^{p-q}]A(x)=[x^p]x^qA(x)$$

• In (3) we apply the binomial theorem and use the binomial series expansion.

• In (4) we use the linearity of the coefficient of operator, apply the rule as in (2) and restrict the upper limit of the outer series since the expoent of $x^{n-k-ml}$ is non-negative. We also use the binomial identity \begin{align*} \binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q \end{align*}

• In (5) we select the coefficient of $x^{n-k-ml}$.