Prueba $\sum_{k=0}^{n-2}{n-k \choose 2} = {n+1 \choose 3}$

Question

Prueba $$\sum_{k=0}^{n-2}{n-k \choose 2} = {n+1 \choose 3}$$

¿Existe alguna relación que pueda utilizar para obtener fácilmente la ecuación anterior?

Answer 1

El lado derecho ${n+1 \choose 3}$ es el número de formas de elegir 3 elementos de $\{1,2,\ldots,n+1\}$ . Dejemos que $A$ denota el conjunto de todos los 3-subsets de $\{1,2,\ldots,n+1\}$ . Queremos demostrar que $|A|$ es igual al lado izquierdo.

Dejemos que $A_i$ denota el conjunto de todos los 3-subsets de $\{1,2,\ldots,n+1\}$ que tienen $i$ como su mayor elemento. Por ejemplo, si $i=n+1$ entonces $A_{n+1}$ es el conjunto de todos los 3-subsets que contienen $n+1$ y el número de formas de elegir los 2 elementos restantes es ${n \choose 2}$ . Por lo tanto, $|A_{n+1}| = {n \choose 2}$ . De manera más general, $|A_i| = {i-1 \choose 2}$ , para $i=3,\ldots,n+1$ porque los 2 elementos restantes deben ser elegidos entre $\{1,\ldots,i-1\}$ . Tenga en cuenta que $i$ tiene que ser al menos 3 porque el mayor de los 3 elementos será al menos 3.

Utilizando el hecho de que el $A_i$ 's $(i=3,4,\ldots,n+1)$ son disjuntos y su unión es toda la $A$ obtenemos la fórmula deseada.

Answer 2

$$\sum_{k=0}^{n-2}\frac{k^2+k(1-2n)+n^2-1}{2}\tag{Simplify what @dixv said}$$ ahora, $$\sum_{k=1}^nk=\frac{n(n+1)}{2}\text{ and }\sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}{6}$$

Espero que te sirva de ayuda.

Answer 3

Para $$S=\sum_{k=0}^{n-2}(n-k)(n-k-1)$$ set $n-k=r$ para conseguir $$S=\sum_{r=1}^nr(r-1)=\sum_{r=1}^nr^2-\sum_{r=1}^nr$$

Ahora usa este O ¿Cómo llegar a la fórmula de la suma de cuadrados de los primeros n números?

Answer 4

Uso de la transformación de índices $m = n - k$ Con la inversión del orden de la suma y la definición del coeficiente binomial en términos de factoriales podemos escribir para $n\ge 2$ : $$\begin{align} \sum_{k=0}^{n-2} \binom{n-k}{2} &= \sum_{m=2}^{n} \binom{m}{2} \\ &= \sum_{m=2}^{n} \frac{m!}{2! (m-2)!} \\ &= \sum_{m=2}^{n} \frac{m(m-1)}{2} \\ &= \sum_{m=1}^n \frac{m(m-1)}{2} \\ &= \frac{1}{2} \sum_{m=1}^{n} m^2 - \frac{1}{2} \sum_{m=1}^n m \\ &= \frac{n(n+1)(2n+1)}{12} - \frac{n(n+1)}{4} \\ &= \frac{1}{6} n^3 + \frac{1}{4} n^2 + \frac{1}{12} n - \left( \frac{1}{4} n^2 + \frac{1}{4} n \right) \\ &= \frac{1}{6} n^3 - \frac{1}{6} n \end{align}$$ donde utilizamos La fórmula de Faulhaber para los números cuadrados piramidales y triangulares.

En el otro lado de la ecuación tenemos: $$\begin{align} \binom{n+1}{3} &= \frac{(n+1)!}{3!(n+1-3)!} \\ &= \frac{(n+1)n(n-1)}{6} \\ &= \frac{n^3 - n}{6} \end{align}$$

Answer 5

Puedes demostrarlo usando funciones generadoras. Queremos demostrar que $$\sum_{m=0}^{n} \binom{m}{2}=\binom{n+1}{3}\tag{1}$$ Utilizar la identidad $$\frac{1}{(1-x)^k}=\sum_{n=0}^\infty \binom{k+n-1}{k-1}x^n.\tag{2}$$ (que puede obtenerse diferenciando repetidamente la serie geométrica) donde $k\geq1$ para conseguir que la función generadora cuya $m$ El coeficiente es $\binom{m+2}{2}$ es $(1-x)^{-3}$ y la función generadora cuya $m$ El coeficiente es $\binom{m}{2}$ es $x^2(1-x)^{-3}$ . Así, $$\sum_{m=0}^{n} \binom{m}{2}= [x^n]\left(\frac{1}{1-x}\frac{x^2}{(1-x)^{3}}\right) = [x^n] \left(\frac{x^2}{(1-x)^{4}}\right)\tag{3} =\binom{n+1}{3}$$ por (2) como se desea, donde $[x^n]$ extrae el coeficiente de $x^n$ .