Coefficient of $x^n$

Question

What is the coefficient of $x^n$ of this following expression:

$$(x+x^2+x^3+ \dots + x^r)^n$$

I tried it but failed. I know that it can be solved by combinations but how? What is the theorem? Is it in generating functions?

Answer 1

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\dd}{{\rm d}}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\ic}{{\rm i}}% \newcommand{\imp}{\Longrightarrow}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert #1 \right\vert}% \newcommand{\yy}{\Longleftrightarrow}$ It should ${\large\it obviously}$ be $\Huge 1$.

In general $\pars{~\mbox{we are assuming}\ r,n \geq 1~}$, \begin{align} &\pars{x + x^{2} + \cdots + x^{r}}^{n} = x^{n}\pars{1 + x + \cdots + x^{r - 1}}^{n} = x^{n}\pars{x^{r} - 1 \over x - 1}^{n} = x^{n}\pars{1 - x^{r}}^{n}\pars{1 - x}^{-n} \\[3mm]&= x^{n}\sum_{\ell = 0}^{\infty}{n \choose \ell}\pars{-1}^{\ell}x^{r\ell} \sum_{\ell' = 0}^{\infty}{-n \choose \ell'}\pars{-1}^{\ell'}x^{\ell'} \\[3mm]&= x^{n}\sum_{\ell = 0}^{\infty}\sum_{\ell' = 0}^{\infty} \pars{-1}^{\ell + \ell'}{n \choose \ell}{-n \choose \ell'} \sum_{n' = 0}^{\infty}x^{n'}\delta_{n',r\ell + \ell'} \\[3mm]&= x^{n}\sum_{n' = 0}^{\infty}x^{n'}\sum_{\ell' = 0}^{\infty} \pars{-1}^{\ell'}{-n \choose \ell'} \sum_{\ell = 0}^{\infty}{n \choose \ell}\pars{-1}^{\ell} \delta_{r\ell,n' - \ell'} = \sum_{n' = n}^{\infty}a_{n'}x^{n'} \end{align}

$$ \pars{x + x^{2} + \cdots + x^{r}}^{n} = \sum_{n' = n}^{\infty}a_{n'}x^{n'} $$ where $a_{n'}$ is given by: $$ a_{n'} = \sum_{\ell' = 0}^{\infty} \pars{-1}^{\ell'}{-n \choose \ell'} \sum_{\ell = 0}^{\infty} {n \choose \ell}\pars{-1}^{\ell}\delta_{r\ell,n' - n - \ell'}\,, \qquad n' \geq n $$

\begin{align} a_{n'}&=\sum_{\ell' = 0}^{\infty}{n + \ell' - 1 \choose \ell'} {n \choose {n' - n - \ell' \over r}}\pars{-1}^{\pars{n' - n - \ell'}/r} \\&\phantom{=}\mbox{where}\quad r \isdiv \pars{n' - n - \ell'}\quad\mbox{and}\quad 0 \leq {n' - n - \ell' \over r } \leq n\tag{1} \end{align} In $\pars{1}$, the second condition is equivalent to: $$ n' -n\pars{1 + r} \leq \ell' \leq n' - n\ {\tt\large \geq 0} $$

Answer 2

Here we suppose $r\geq 2$. We have $$(x + x^2 + \cdots + x^r)^n$$ $$=x^n(1+x+\cdots+x^{r-1})^n$$ $$=x^n(1+xp(x))^n$$ where $$p(x) = 1 + x + \cdots + x^{r-2}.$$ Next we use the binomial theorem to write

$$=x^n(1+xp(x))^n$$ $$= x^n\left(\sum_{k=0}^n \binom{n}{k}x^kp(x)^k\right)$$ $$= \sum_{k=0}^n \binom{n}{k}x^{n+k}p(x)^k$$ and we see the coefficient of $x^n$ is $\binom n 0 = 1$.