Coefficient of $x^n$ in the series

Question

How will we find the coefficient of $x^n$ in the following series: $$(1+x+2x^2+3x^3+...)^n$$

Please suggest if there is some formula or if it can be computed using the computer in $\log n$ time. I have figured out the differentiation approach which is slow. Thanks in advance.I am guessing matrix multiplication/exponentiation and linear algebra could help. Edit: I tried multinomial theorem too, but couldn't build on the solution as it requires the coefficients to be constant.

Answer 1

Clearly, for every $\lvert x\rvert<1$: \begin{align} 1+x+2x^2+3x^3+\cdots&=1+x\frac{d}{dx}\big(1+x+x^2+\cdots\big)= 1+x\frac{d}{dx}\left(\frac{1}{1-x}\right)\\ &=1+\frac{x}{(1-x)^2}. \end{align} Therefore \begin{align} f(x) &=(1+x+2x^2+3x^3+\cdots)^n=\left(1+\frac{x}{(1-x)^2}\right)^n \\ &= \sum_{k=0}^n\binom{n}{k}\frac{x^k}{(1-x)^{2k}} =\sum_{k=0}^n\binom{n}{k} \,x^k\Big(\sum_{j=0}^\infty s_{k,j}x^j \Big), \end{align} where $\sum_{j=0}^\infty s_{k,j}x^j=(1-x)^{-2k}$. The coefficient of $x^n$ is equal to $$ c_n=\sum_{k=0}^n\binom{n}{k}s_{k,n-k}, $$ where $s_{k,n-k}$ is the coefficient of $x^{n-k}$ of $(1-x)^{-2k}$. But $$ s_{k,n-k}= \left.\frac{1}{(n-k)!}\frac{d^{n-k}}{dx^{n-k}}\right|_{x=0}\left(\frac{1}{(1-x)^{2k}}\right) =\frac{1}{(n-k)!}\cdot\frac{(k+n-1)!}{(2k-1)!}=\binom{k+n-1}{n-k}, $$ and thus $$ c_n =\sum_{k=0}^n\binom{n}{k}\binom{n+k-1}{n-k}. $$

Answer 2

Hint:(Assuming $|x|<1$)

$(1+x+2x^2+3x^3+.....)^n$

$=((1+x+x^2+....)+(x^2+x^3+x^4+....)+(x^3+x^4+x^5+.....)+......))^n$

$=(\frac{1}{x-1}+x^2.\frac{1}{x-1}+x^3.\frac{1}{x-1}+....)^n$

$=(\frac{1}{x-1})^n(1+x^2+x^3+....)^n$

$=(\frac{1}{x-1})^n(1+\frac{x^2}{x-1})^n$

Answer 3

Hint: $$ 1+x+2x^2+\cdots+x^n+\cdots=1+x(1+2x+n x^{n-1}+\cdots)=1+\frac{x}{(1-x)^2}. $$ Then $$ (1+x+2x^2+\cdots+x^n+\cdots)^n=\sum_{i=0}^n {n \choose i}\frac{x^i}{(1-x)^{2i}}. $$ Now you need to calculate $$ [x^n]\frac{x^i}{(1-x)^{2i}}, i \leq n, $$ it is doable.

Answer 4

$$ \begin{align} f(x)&=1+x+2x^2+3x^3+4x^4+\dots\\ xf(x)&=\hphantom{1+\,}x+\hphantom{2}x^2+2x^3+3x^4+\dots\\ (1-x)f(x)&=1\hphantom{+x\,\:}+\hphantom{2}x^2+\hphantom{2}x^3+\hphantom{3}x^4+\dots\\ &=1\hphantom{+x\,\:}+\frac{x^2}{1-x}\\ f(x)&=1+\frac{x}{(1-x)^2}\\ f(x)^n&=\sum_{k=0}^n\sum_{m=k}^\infty\binom{n}{k}x^k\binom{-2k}{m-k}(-x)^{m-k} \end{align} $$ The coefficient of $x^n$ is $$ \sum_{k=0}^n\binom{n}{k}\binom{-2k}{n-k}(-1)^{n-k}=\sum_{k=0}^n\binom{n}{k}\binom{n+k-1}{n-k} $$