combinatorics: sum of product of integer compositions I am trying to solve a problem from Stanley's book, it says:
Fix $k,n \in \mathbb{P}$. Show that:
\begin{align}
\sum a_1 a_2 \cdots a_k = \binom{n+k-1}{2k-1}
\end{align}
where the sum ranges over all compositions $(a_1 , a_2 , \ldots , a_k)$ of $n$ into $k$ parts.
I am trying to reason like this:
we need to find the coefficient $c_n = \sum a_1 a_2 \cdots a_k$ from this generating function --
\begin{align}
\sum_n c_n x^n &= \sum_n \sum a_1 a_2 \cdots a_k x^n \\ 
&= \sum_n \sum a_1 a_2 \cdots a_k x^{a_1 + a_2 + \cdots + a_k}\\
&= \sum_n \sum a_1x^{a_1} a_2x^{a_2} \cdots a_kx^{a_k}
\end{align}
after that, I have no clue, how do I solve this ? 
moreover, what is the range in the inner sum ?

If we consider Mark Riedel's answer, and assume $n=4$, $k=2$; then the sum will be 
\begin{align}
\sum (z + 2z^2)^2 = z^2 + 4z^3 + 4z^4
\end{align}
On the other hand the compositions will be $(1,3), (2,2), (3,1)$, therefore the above sum will be counted as:
\begin{align}
(1.3)z^{1+3} + (2.2)z^{2+2} + (3.1)z^{3+1} &= 1z^1.3z^3 + 2z^2.2z^2 + 3z^3.1z^1\\ 
&= 3z^4 + 4z^4 + 3z^4 = 10z^4
\end{align} 
what's going on? what am I missing?

Compositions of $n$ into $k$ parts can be represented as a string of $n$ stars and $k-1$ bars. The $k-1$ bars break the stars into $k$ groups, and the number of stars in the $i^{th}$ group represents $a_i$.
For each of these compositions, we are adding $a_1a_2\dots a_k$. This represents the number of ways to choose one star from each of the $k$ blocks, and color it red. For example, with $n=6, k=3$, and the composition $\star\star|\star\star\star|\star$, the number of ways to color one star in each group red like $\star\color{red}\star|\star\color{red}\star\star|\color{red}\star$ would be $2\cdot 3\cdot 1$.
However, there is a more direct way to count these arrangements of black  stars, red stars, and bars. If you ignore the black stars, then what remains is an alternating pattern of red stars and bars; in the example, this is $\color{red}\star|\color{red}\star|\color{red}\star$. There are $k+(k-1)=2k-1$ symbols which are red stars or bars, and $n+k-1$ symbols total. Therefore, there are $\binom{n+k-1}{2k-1}$ arrangements, since an arrangement is specified by choosing which of the $2k-1$ symbols are red stars or bars, and then assigning these in an alternating fashion.
