How to find the closed form for this polynomial generating function with 2 variables 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]$
 A: 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}$.
