Es la similitud entre la suma de la primera $n$ números) = $\frac{n(n+1)}{2}$ e $\binom{n}{2} = \frac{n(n-1)}{2}$ una coincidencia?

Question

Estas fórmulas son iguales el uno al otro, a excepción de una-por-un cambio. Es esto una coincidencia? La derivación de

$$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$

tiene que ver con el emparejamiento de elementos. Así que están relacionados de manera significativa?

Answer 1

No, esto no es una coincidencia en el sentido de que hay una prueba de lo que explica por qué debe ser verdadera. Este es un método estándar conocido como "doble contabilidad".

Considere la posibilidad de tener $n$ de la gente en una fiesta, que nunca han conocido. Queremos contar el número de apretones de manos. Cada par de personas de estrechar la mano de una vez.

Una forma de hacerlo es considerar a cada persona individualmente. La primera persona que hace que $n-1$ apretones de manos, luego la segunda persona hace $n-2$ apretones de manos, etc., hacia la segunda a la última persona que $1$ apretón de manos.

Otra forma es hacerlo combinatorically. Estamos buscando parejas de personas sin relación de orden, es decir, $\binom{n}{2}$. Por lo tanto:

$$ \binom{n}{2} = 1 + 2 + \cdots + (n-1) $$

Answer 2

No creo que el "emparejamiento" de los números en la prueba usual de la suma tiene ninguna conexión con los dos elementos, subconjuntos contado por $n\choose2$, pero he aquí una manera de ver una conexión entre dos elementos, subconjuntos de un conjunto de $n$ elementos y la suma de los números de $1$ (o cero) a $n-1$. La idea es similar a lo que George describe en su respuesta.

Consideremos el conjunto $S=\{0,1,\dots,n-1\}$. Quieres saber si es una coincidencia que la suma de los números en $S$ es igual al número de dos elementos, subconjuntos de $S$.

Cada uno de los dos elementos subconjunto de $S$ tiene un único elemento mayor (que es un elemento de $S$). No hay dos elementos, subconjuntos en que $0$ es el elemento más grande. Hay uno de los dos elementos de un subconjunto en el que $1$ es el elemento más grande, y así sucesivamente. Para cada una de las $k\in S$ hay $k$ dos elementos, subconjuntos en que $k$ es el elemento más grande, y así sucesivamente.

Dicho de otra manera, cada número $k\in S$ aparece como el valor más grande en exactamente $k$ de los dos elementos, subconjuntos de $S$.

Por lo tanto, para contar el número de dos elementos, subconjuntos de $S$, podemos simplemente sumar los números en $S$, el resultado es $0+1+\cdots+(n-1)$.