# 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.

• Is $k$ fixed? (I assume that $n$ is, though strictly speaking this isn't clear either.) – darij grinberg Jan 20 '16 at 20:21
• Also, is "the $r^k$-coefficient of $\left(1+r^0\right)\left(1+r^1\right)\cdots\left(1+r^n\right)$" a closed form expression for you? Recall that lists $\left(i_1, i_2, \ldots, i_k\right)$ of integers satisfying $0 \leq i_1 < i_2 < \cdots < i_k \leq n$ are in bijection with $k$-element subsets of $\left\{0,1,\ldots,n\right\}$. – darij grinberg Jan 20 '16 at 20:22
• Yes, $n,k$ are all fixed. @darijgrinberg, Yes, actually I got the expression in that manner. – Samrat Mukhopadhyay Jan 20 '16 at 20:28
• You can write the generating function: $$f_n(x)=\prod_{i=0}^{n} (r^i+x)$$ Then the coefficient of $x^{n-k}$ is the the above sum when you are looking for fixed $k$. Not sure how that helps. – Thomas Andrews Jan 20 '16 at 20:35
• @ThomasAndrews, that is how I found my expression. So, in other words my question can be framed to ask: What is the coefficient of $x^{n-k}$ in the monomial with roots $r^0,\ r^1\cdots,\ r^{n}$. – Samrat Mukhopadhyay Jan 20 '16 at 20:38

## 3 Answers

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})$.

• Oh, great! Thanks for the answer. Do you know any reference where I can get a discussion about this kind of sums? – Samrat Mukhopadhyay Feb 12 '16 at 5:07
• @SamratMukhopadhyay Unfortunately I do not know any book on those things I have derived the sum of power functions over a simplex myself just by using the geometric sum formula and induction. Note that the later formula is very useful since it can be used for generating closed form expressions for sums of the kind \begin{equation} \sum\limits_{0\le i_1 \le \cdots \le i_k \le n}\binom{n_1 i_1+ n_2 i_2 + \cdots+ n_k i_k}{p }\end{equation} for some integer or even real numbers $n_1,\cdots,n_k$. – Przemo Feb 12 '16 at 15:06
• Oh, nice work then! – Samrat Mukhopadhyay Feb 15 '16 at 5:45
• @SamratMukhopadhyay I was wondering if you can help me with the following. Clearly if we take $r \rightarrow 1$ in the $S_k(n)$ we must be getting $\binom{n+1}_{k}$. Unfortunately the terms in the sum are singular. Using Mathematica I have checked that $\left(\frac{1}{k!} \frac{d^k}{d r^k} r^k \left(S_k(n)_{r:>1-r}\right)\right)_{r:>0}$ = \binom{n+1}{k}$. Can we actually work out the right hand side analyticaly and show that this identity indeed holds true? – Przemo Feb 29 '16 at 12:04 • I think the limit works only when we take the sum with all terms together. – Samrat Mukhopadhyay Feb 29 '16 at 15:06 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)$. • Thanks for this answer too. – Samrat Mukhopadhyay Feb 15 '16 at 5:45 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.