Coefficient of $x^n$ in the series 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. 
 A: 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}.
$$
A: $$
\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}
$$
A: 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$
A: 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.
