# 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.) Jan 20, 2016 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\}$. Jan 20, 2016 at 20:22
• Yes, $n,k$ are all fixed. @darijgrinberg, Yes, actually I got the expression in that manner. Jan 20, 2016 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. Jan 20, 2016 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}$. Jan 20, 2016 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: $$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}}$$ 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? Feb 12, 2016 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 $$\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 }$$ for some integer or even real numbers $n_1,\cdots,n_k$. Feb 12, 2016 at 15:06
• Oh, nice work then! Feb 15, 2016 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? Feb 29, 2016 at 12:04 • I think the limit works only when we take the sum with all terms together. Feb 29, 2016 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: $$S_k(n) = \sum\limits_{l=\binom{k}{2}}^{\binom{k}{2}+k(n-k)} \theta_{k,l}^{(n)} r^l$$ where $$\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}$$ where$p_j := l - \binom{k-j}{2} - j (n+1)$. • Thanks for this answer too. Feb 15, 2016 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 $${\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}$$ 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: $$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}$$ 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: $$\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}$$ 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: $$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}$$ It would be interesting to prove the identity involving the Stirling numbers of the first kind.