Cuál es la suma de productos de pares de enteros: $\sum_{0\le i<j\le n} ij$ ?

Question

Es bien sabido que $S_1\equiv \sum_{k=0}^n k = \binom{n+1}{2}$ . Cómo se generaliza esta fórmula para sumas de productos de pares de enteros más pequeños que $n$ ? En el caso más sencillo, se trata de $$S_2 \equiv \sum_{0\le i<j\le n}ij = \frac12 \left(\sum_{i,j=0}^n ij - \sum_{i=0}^n i^2\right).$$ Puedo reescribir esto como $$S_2 = \sum_{i=1}^n i \sum_{j=i+1}^n j = \sum_{i=1}^n i \left[\binom{n+1}{2}-\binom{i+1}{2}\right].$$ ¿Existe una fórmula más explícita para ello? ¿O quizás un argumento más directo o geométrico para llegar a esto?

En términos más generales, ¿existen fórmulas para $S_k\equiv \sum_{0\le i_1<...<i_\ell\le n}i_1\cdots i_\ell$ ?

Uno de los contextos en los que surgen estos números es en los coeficientes de $s!/(s-k)!$ con $k\le s$ : $$\frac{s!}{(s-k)!} = \sum_{j=0}^k S_k s^k.$$

Answer 1

Si vas un paso más allá en tu primera línea, entonces puedes escribir esto como

$$ S_2 = \frac{1}{2}(\sum_{i=0}^n i)^2 - \frac{1}{2}\sum_{i=0}^n i^2.$$

La primera suma es $n(n+1)/2$ . El segundo es $n(n+1)(2n+1)/6$ . En conjunto, pues, esto da

$$ S_2 = \frac{n^2(n+1)^2}{8} - \frac{n(n+1)(2n+1)}{12},$$

que puede simplificarse para adaptarse. (En particular, por ejemplo, $S_2=n^4/8 + O(n^3)$ ).