# Sum of increasing integer numbers

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.

• Have you tried the easiest cases, like $k=1,k=2,k=n-1$ or $k=n$? – Arthur Mar 30 '15 at 20:16

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

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$

• +1, nicely following a Master, or, should we say a Prince? – Did Mar 30 '15 at 21:17
• I think that it's preferable to say master As we are here to find our own rich mathematical life, an share that life with others, and masters are always a part of that life! – Elaqqad Apr 1 '15 at 9:25
• Search for "Princeps mathematicorum" in there. – Did Apr 1 '15 at 13:37

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