Calculation a closed form for the sum Please help me to calculate this sum in a closed form:
$$
\sum\limits_{1\ \leq\ i_{1}\ <\ i_{2}\ <\ \cdots\ <\ i_{k}\ \leq\ n}
\left(i_{1} + i_{2} + \cdots + i_{k}\right).
$$
Here $n$, $k$ are positive integer numbers; $k < n$.
I think that it may be reduce to binomial coefficients, but I cannot understand how to do this.
Thank you very much in advance for your help !.
 A: The sum 
$$
\sum_{j} i_j
$$
can be computed alternatively by counting how many times for $i_j=x$ appeared; the answer is $\binom{n-1}{k-1}$: fix $x$, there are $\binom{n-1}{k-1}$ ways to choose other $k-1$ numbers from $\{1,\cdots,n\}\backslash \{x\} $. Therefore, the sum is simply
$$
\sum_{x} x\binom{n-1}{k-1}=\binom{n+1}{2}\binom{n-1}{k-1}.
$$
A: The answer is a polynomial in $n$ of degree $k+1$, so if nothing else you can just figure out the answer for $n = 1,2,\ldots,k+1$ and then solve for the polynomial coefficients that fit the polynomial, and thus get the answer for any fixed $k$. Alternatively you can solve for $k$ in increasing order using the recurrence below. Anyway, to see the answer is a polynomial in $n$ of degree $k+1$, note that for $k=1$ you get $\sum_{i=1}^n i = n(n+1)/2$ which is a polynomial in $n$ of degree $2$. Then, for $k \geq 1$, let $P_k(n)$ be the polynomial of degree $k+1$ that is the answer for $k,n$. Then by choosing the last number $i_{k+1}$ to be between $1$ and $n$, we see that $P_{k+1}(n) = \sum_{m=1}^n P_k(m)$ which is a polynomial in $n$ of degree $k+2$ because $\sum_{m=1}^n m^{k'}$ for any power $k'$ is a polynomial in $n$ of degree $k'+1$, by theorem. This gives an alternate way to compute the polynomial $P_{k+1}(n)$, if you write $P_k(m)$ as a sum of basis polynomials that you can easily sum from $m = 1$ to $n$.
