Coefficient of polynomial of $x^k$

Question

Consider a polynomial of power n:

$P(x)=1+x+x^2+\dots+x^n$

How do I find coefficient of $x^k$, where $0\le k\le 3n$ of the polynomial $P^3(x)$?

I have tried plugging in different values of $n$ to find the logic and here are my results:

• There is a symmetry line of $k=\frac{3n}{2}$
• For $k\le n$ the coefficient is always given by $\frac{k(k+1)}{2}$

Answer 1

Let's simplify the expression $ (1 - x^{n+1})^m $ using some familiar techniques. When the power is a positive integer, we can leverage the standard binomial theorem:

$$ (1 - x^{n+1})^m = \sum_{i=0}^m (-1)^i \binom{m}{i} x^{(n+1)i} $$

On the other hand, for $ (1 - x)^{-m} $, where the power is a negative integer, we turn to the negative binomial theorem:

$$ (1 - x)^{-m} = \sum_{j=0}^\infty \binom{m+j-1}{j} x^j $$

Now, let's combine these results by multiplying the two sums:

$$ \left( \frac{1 - x^{n+1}}{1 - x} \right)^m = \sum_{i=0}^m \sum_{j=0}^\infty (-1)^i \binom{m}{i} \binom{m+j-1}{j} x^{(n+1)i+j} $$

This expression reveals the coefficient for $x^k$, which is given by:

$$ \sum_{\substack{0 \leq i \leq m, \\ j \geq 0 \\ (n+1)i+j=k}} (-1)^i \binom{m}{i} \binom{m+j-1}{j} $$

now you can use this result directly to your problem

any combinotorics books will must have this kind of problems

Answer 2

We consider \begin{align*} P(x)=1+x+\cdots+x^n=\frac{1-x^{n+1}}{1-x} \end{align*} We use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series.

We obtain for $0\leq k\leq 3n$: \begin{align*} \color{blue}{[x^k]P^{3}(x)}&=[x^k]\left(\frac{1-x^{n+1}}{1-x}\right)^3\\ &=[x^k]\left(1-3x^{n+1}+3x^{2n+2}\right)\sum_{q=0}^{\infty}\binom{-3}{q}(-x)^q\tag{1}\\ &=\left([x^k]-3[x^{k-(n+1)}]+3[x^{k-(2n+2)}]\right)\sum_{q=0}^{\infty}\binom{q+2}{2}x^q\tag{2}\\ &\,\,\color{blue}{=\binom{k+2}{2}-3\binom{k-n+1}{2}[[k\geq n+1]]}\\ &\qquad\quad\,\,\color{blue}{+3\binom{k-2n}{2}[[k\geq 2n+2]]}\tag{3} \end{align*}

Comment:

• In (1) we expand $\left(1-x^{n+1}\right)^3$ and omit the term with $x^{3n+3}$ as it does not contribute to $[x^k]$. We also perform a binomial series expansion.

• In (2) we use the linearity of the coefficient of operator and apply the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$. We also use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q=\binom{p+q-1}{p-1}(-1)^q$.

• In (3) we select the coefficients of $[x^{k-f(n)}]$ and use Iverson brackets for a compact presentation.