Is there a closed form expression for the following sum? Is there a closed form expression for the following sum? $$\sum_{0\le i_1<i_2<\cdots<i_k\le n}r^{i_1+i_2+\cdots+i_k}$$
I can understand that there are $\binom{n}{k}$ such terms and the values that $i_1+\cdots+i_k$ can take vary from $\frac{k(k-1)}{2}$ to $k(n-k)+\frac{k(k+1)}{2}$. So it remains to find how often the term $\sum_{j=1}^k i_j=l$ is found as an exponent in the above sum. Can anyone give some idea? Thanks.
 A: This is a particular case of a more general formula that I posted in here Sum of power functions over a simplex . By denoting your sum as $S_k(n)$ we have:
\begin{equation}
S_k(n) = \sum\limits_{j=0}^{k}
\frac{(-1)^j r^{\frac{1}{2} (-j+k-1) (k-j)+j (n+1)}}{(r;r)_j (r;r)_{k-j}}
\end{equation}
where $(r;r)_j := \prod\limits_{l=0}^{j-1} (1-r^{l+1})$.
A: By using my first answer and the definition of the multiple sum and Cauchy theorem from complex analysis we readily provide another closed form solution:
\begin{equation}
S_k(n) = \sum\limits_{l=\binom{k}{2}}^{\binom{k}{2}+k(n-k)} 
\theta_{k,l}^{(n)} r^l
\end{equation}
where 
\begin{equation}
\theta_{k,l}^{(n)} := \sum\limits_{j=0}^k (-1)^j \frac{1_{0\le p_j \le l}}{p_j !} \frac{d^{p_j}}{d z ^{p_j}} \left.\left( \frac{1}{(z;z)_j (z;z)_{k-j}} \right)\right|_{z=0}
\end{equation}
where $p_j := l - \binom{k-j}{2} - j (n+1)$.
A: In here we calculate the limit of $S_k(n)$ when $r$ goes to unity. It is easy to see that each of the terms in the sum over $j$ behaves like $O(\frac{1}{(1-r)^k})$ in that limit. Therefore in order to get the limit we need to extract the coefficient at $\frac{1}{(1-r)^k}$. In other words we need to compute:
\begin{eqnarray}
\left.\frac{(-1)^k}{k!} \frac{d^k}{d r^k} r^k \left( \left. S_k(n) \right|_{r \rightarrow 1-r} \right) \right|_{r\rightarrow 0} =
\frac{1}{k!} \sum\limits_{j=0}^k \sum\limits_{q_2=0}^k \binom{k}{q_2}
(-1)^{j+k+q_2} \left(\binom{k-j}{2} + j \cdot(n+1)\right)_{(k-q_2)} \cdot
{\mathcal A}^{(j,k-j)}_{q_2}
\end{eqnarray}
where 
\begin{equation}
{\mathcal A}^{(j,k-j)}_{q_2} := \frac{d^{q_2}}{d r^{q_2}} \left.\left(\frac{r^k}{(1-r;1-r)_j(1-r;1-r)_{k-j}} \right)\right|_{r\rightarrow 0}
\end{equation}
Now the situation seems hopeless. On the face of it it will not be possible to find a closed form expression for the coefficients above and therefore it might seem we will never evaluate the sum. However, let us brace ourselves and make a step further. We use the Chu-Vandermonde identity to expand the right hand side. We have:
\begin{equation}
rhs = \frac{1}{k!}\sum\limits_{j=0}^k \sum\limits_{q_3=0}^k (j (n+1))_{(q_3)} \cdot \sum\limits_{q_2=0}^{k-q_3} (-1)^{k+q_2+j} \frac{k!}{q_2!q_3!(k-q_2-q_3)!} \cdot \binom{k-j}{2}_{(k-q_2-q_3)} \cdot {\mathcal A}^{(j,k-j)}_{q_2}
\end{equation}
Now a miracle occurs. We have checked using Mathematica that for fixed $q_3$ the sum of the right hand side is just equal to a power of $(1+n)$ multiplied by a Stirling number of the first kind. In other words we have:
\begin{equation}
\left(n+1\right)^{q_3} S^{(k)}_{q_3} = \binom{k}{q_3}
\frac{d^{q_3}}{d r_1^{q_3}} \frac{d^{k-q_3}}{d r^{k-q_3}}
\left.\left(
\sum\limits_{j=0}^k (-1)^j \frac{(1-r)^{\binom{k-j}{2}} (1-r_1)^{j (n+1)}}{(1-r;1-r)_j \cdot (1-r;1-r)_{k-j}} \cdot r^k
\right)
\right|_{r=0,r_1=0}
\end{equation}
for $k \in {\mathbb N}_+$ and $q_3=0,\cdots,k$.
Inserting the above to the right hand side of the equation in question gives:
\begin{equation}
rhs = \frac{1}{k!} \sum\limits_{q_3=0}^k (n+1)^{q_3} S^{(k)}_{q_3} = \frac{(n+1)_{(k)}}{k!} = \binom{n+1}{k}
\end{equation}
It would be interesting to prove the identity involving the Stirling numbers of the first kind.
