Sum of increasing integer numbers

Question

Please help me to calculate this sum: $$ \sum\limits_{1\leq i_1 < i_2 <\ldots i_k \leq n} (i_1+i_2+\ldots+i_k). $$

Here $n$ and $k$ are positive integer numbers, and all the numbers $i_1, i_2, \ldots, i_k$ are positive integers.

Answer 1

Double-counting is the key. Given any $m\in[1,n]$, it belongs to exactly $\binom{n-1}{k-1}$ $k$-tuples $(i_1,\ldots,i_k)$ with $1\leq i_1<i_2\ldots<i_{n-1}<i_n\leq n$, hence:

$$ \sum_{1\leq i_1<\ldots<i_n\leq n}(i_1+\ldots+i_k) = \sum_{m=1}^{n}m\binom{n-1}{k-1}=\binom{n+1}{2}\binom{n-1}{k-1}.$$

Answer 2

Using the Gauss method for sums: $$2S= \sum_{1\leq i_1<\ldots<i_n\leq n}(i_1+\ldots+i_k)+\sum_{1\leq i_1<\ldots<i_n\leq n}((n+1-i_1)+\ldots+(n+1-i_k))=(n+1)k \dbinom{n}{k} $$

because there is exactly $\binom{n}{k}$ $k$-tuples $(i_1,\ldots,i_k)$ with $1\leq i_1<i_2\ldots<i_{n-1}<i_n\leq n$

Answer 3

The reader may be surprised to learn that this can be solved with cycle indices.

Suppose we seek to evaluate $$\sum_{1\le q_1 \lt q_2 \lt \cdots \lt q_k \le n} (q_1+q_2+\cdots+q_k).$$

Using the cycle index $Z(P_k)$ of the unlabeled set operator $\mathfrak{P}_{=k}$ this is $$\left. \frac{d}{dz} Z(P_k)(z+z^2+\cdots+z^n)\right|_{z=1}.$$

The OGF of the set operator is $$G(w) = \exp\left(a_1 w - a_2 \frac{w^2}{2} + a_3 \frac{w^3}{3} - \cdots\right).$$

Doing the substitution we obtain $$H(w, z) = \exp\left(\sum_{q\ge 1} \frac{(-1)^{q-1} w^q}{q} \sum_{p=1}^n z^{pq}\right).$$

Differentiate to get $$\frac{d}{dz} H(w,z) = \exp\left(\sum_{q\ge 1} \frac{(-1)^{q-1} w^q}{q} \sum_{p=1}^n z^{pq}\right) \sum_{q\ge 1} \frac{(-1)^{q-1} w^q}{q} \sum_{p=1}^n pq z^{pq-1}$$

and set $z=1$ to obtain $$\left.\frac{d}{dz} H(w,z)\right|_{z=1} = \exp\left(n\log(1+w)\right) \sum_{q\ge 1} (-1)^{q-1} w^q \sum_{p=1}^n p \\ = {n+1\choose 2} (1+w)^n \frac{w}{1+w} = {n+1\choose 2} w (1+w)^{n-1}.$$

Extracting coefficients from this we finally obtain $$[w^k] {n+1\choose 2} w (1+w)^{n-1} = {n+1\choose 2} [w^{k-1}] (1+w)^{n-1} = {n+1\choose 2} {n-1\choose k-1}.$$