Show that the coefficient of $x^i$ in $(1+x+\dots+x^i)^j$ is $\binom{i+j-1}{j-1}$ Show that $$\text{ The coefficient of }  x^i \text{ in } (1+x+\dots+x^i)^j \text{ is } \binom{i+j-1}{j-1}$$
I know that we have:
$\underbrace{(1+x+\dots+x^i) \cdots (1+x+\dots+x^i)}_{j\text{ times}}$
My first problem how to explain that and why -1 and not $\binom{i+j}{j}$ ? its because the $1x^0$ ?
Thank you
 A: If you pick $x^{n_r}$ from the rth factor, then to get to $x^i$ requires that:
$$\sum_{r=1}^{j} n_r= i$$
So, the coefficient of $x^i$ is the number of solutions to the above equation, how many different choices for the $n_r$ with the $n_r$ ranging from 0 to i are there? Suppose that you have i identical objects that can be colored using j different colors. A particular coloring can be represented by specifying for each r, how many objects have the rth color. Then denoting the number of objects with color r by $n_r$, you see that this is identical to the above problem. The $n_r$ range from 0 to j and they must sum to i and each solution is a possible coloring.
So, how do we count the number of colorings? We can represent a coloring by a string like 000|0||0000|00|.... where the 0's denote the objects and the |'s are the separations between the objects that get one particular color to the next. The number of 0's is then equal to i, the number of |'s is equal to j-1, because you need one less than the number of colors to separate the j colors. The total number of different strings of i 0's and j-1 |'s is given by $\binom{i+j-1}{j-1}$
A: Consider a typical term of $(1+x+\ldots+x^i)^j$ after you multiply everything out but before you collect terms: it has the form
$$x^{n_1}x^{n_2}\ldots x^{n_j}\;,$$
where each $n_k$ is a non-negative integer, and $n_1+n_2+\ldots+n_j=i$. Conversely, every $j$-tuple of non-negative integers whose sum is $j$ corresponds to a term in the product. Thus, the coefficient of $x^i$ after you collect terms is the number of solutions to $n_1+n_2+\ldots+n_j=i$ in non-negative integers. The reason that this is
$$\binom{i+j-1}{j-1}=\binom{i+j-1}i$$
is explained fairly clearly in this Wikipedia article and also in this one; both are worth reading for more than just this result.
A: As far as the coefficient of $x^i$ is concerned, we might just as well look at
$$(1+x+x^2+x^3+\cdots)^j,$$
that is, at $\left(\frac{1}{1-x}\right)^j$. The Maclaurin series expansion of $(1-x)^{-j}$ has coefficient of $x^i$ equal to $\frac{j(j+1)(j+2)\cdots (j+i-1)}{i!}$. This is $\frac{(j+i-1)!}{(j-1)!i!}$, which is $\binom{j+i-1}{i}$. 
