How to find the coefficients of the $k$-th term of $\left(\frac{x^n - 1}{x - 1}\right)^m$ for arbitrary $k$, $m$, and $n$?

Question

I am trying to find an equation for finding the coefficient of the $k$th term of the expansion of $\left(\frac{x^n - 1}{x - 1}\right)^m$ for any $n$, $m$, and $k$.

So, far I've managed to find A277950 the terms for $m = 5$. I however have not been able to figure out what $k$ is in their formula for the sequence, and I can't find a way to generalize it for $m \neq 5$.

I have similarly written a python program to find the coefficients, which works by looping through the integers in $[1, n]$, $m$ times and then counting the number of times each number appears. Printing the number of time each number appears in order yields the coefficients of the expansion. I have no idea why this is working, but for every set of numbers I've tried it has worked correctly.

Answer 1

It is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. This way we can write e.g. \begin{align*} [x^k](1+x)^m=\binom{m}{k} \end{align*}

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

Comment:

• In (1) we apply the binomial series expansion with $\alpha=-m$.

• In (2) we expand the binomial $(1-x)^m$ and use the binomial identity

\begin{align*} \binom{-p}{q}=\binom{p+q-1}{q}(-1)^q \end{align*}

• In (3) we use the linearity of the coefficient of operator and apply the rule $$[x^{p-q}]A(x)=[x^p]x^qA(x)$$ We also set the upper limit of the series to $k$ since the exponent of $x^{k-j}$ is non-negative.

• In (4) we exchange the order of summation of the outer sum by replacing $j\rightarrow k-j$.

• In (5) we select multiples of $n$ of the index $j$ since we have multiples of $n$ in the exponent $x^{nl}$ in the inner sum.

• In (6) we select the coefficient of $[x^{nj}]$ in the inner sum by setting $l=j$.

Answer 2

As user35508 remarked, $(x^{n}-1)(x-1) = 1+x+\cdots +x^{n-1}$. Now, as we raise it to the $m$-th power, we need to open brackets. How many times $x^k$ appears? Each factor will contribute $x^i$ for some $i$ exactly once, so the coefficients of $x^k$ equals to the number of solutions to the equation $$ X_1 + \cdots + X_m = k $$ with $0\leq X_i\leq n-1$. This number can be explicitly expressed in terms of binomial coefficients. For example, if $n-1\geq k$ it is the same as unordered samples with replacement, so the $k$-th coefficient equals $\binom{m+k-1}{k}$.

What happens when $n-1<k$, I leave it for you to solve...