¿Alguna razón elegante detrás de la siguiente identidad?

Question

$$ \sum_{i=1}^{n-k+1} {{n - i}\, seleccione{k - 1}} i = {{n + 1}\, seleccione{k + 1}} $$

Tenga en cuenta que la identidad es obviamente cierto para$k=1$$k=2$.

Para $k=1$
lado izquierdo = $\sum_{i=1}^n i = \frac{n(n+1)}{2} = {{n + 1}\choose{2}}$ = lado derecho

Para $k=2$
lado izquierdo = $\sum_{i=1}^n (n-i)i = \frac{n^2(n+1)}{2} -\frac{n(n+1)(2n+1)}{6} = \frac{(n-1)n(n + 1)}{6} = {{n+1}\choose{3}}$ = lado derecho

He probado la anterior identidad, utilizando algunas aburrido álgebra. He utilizado el truco de que el lado izquierdo es igual a los coeficientes de $x^{k - 1}$ en la serie de $\sum_{i=1}^{n-k+1} i(1 + x)^{n-i}$.

El uso de la progresión geométrica truco, podemos demostrar que

$$\sum_{i=1}^{n-k+1} i(1 + x)^{n-i} = -\frac{(1+x)^{k-1}(n-k+1)}{x} + \frac{(1+x)^{n+1}}{x^2} - \frac{(1+x)^k}{x^2}.$$ Claramente los coeficientes de $x^{k-1}$ en el lado derecho es ${{n+1}\choose{k+1}}$.

Answer 1

Considera un$(k+1)$ - subconjunto de elementos$S \subset \{1, \ldots, n+1\}$, y deja que$n-i+1$ sea el segundo elemento más grande. Hay$i$ opciones posibles para el elemento más grande de las opciones$S$ y${n-i \choose k-1}$ para el resto del conjunto. Agrupar los subconjuntos$(k+1)$ - element de acuerdo con su segundo elemento más grande de esta manera da la identidad deseada.