Mostrando$\sum_{k = 2}^n \binom{k}{2} \binom{n}{k} = \binom{n}{2} 2^n$ sin inducción.

Question

¿Cómo pruebo la identidad$$\sum_{k = 2}^n \binom{k}{2} \binom{n}{k} = \binom{n}{2} 2^{n-2} de manera combinatoria, es decir, contando la cardinalidad del mismo conjunto de dos maneras diferentes? Sé cómo hacerlo por inducción, pero no sé cómo hacerlo combinatoriamente. Gracias por adelantado.

Answer 1

Creo que hay un error, y debe ser $2^{n - 2}$ en lugar de $2^n$. Por ejemplo, si $n = 2$ el lado izquierdo es$1$, mientras que el lado derecho sería $2^2$.

---

Tiene un cuadro que contenga $n$ elementos; usted elija $k$ de ellos fuera de la caja y, a continuación, elija $2$ estos $k$. El resultado final es que usted elija exactamente $2$ elementos de $n$. Pero nuestros dos elementos están seleccionados como muchas veces hay grupos que contienen los dos elementos - este es igual al número de subconjuntos de los restantes $n - 2$ elementos - que es $2^{n - 2}$.

Por lo tanto, la suma es

$$\sum_{k = 2}^{n} \binom{n}{k} \binom{k}{2} = 2^{n - 2} \binom{n}{2}$$

Answer 2

Supongamos que usted está interesado en contar cuántos equipos puede hacer con $n$ de las personas, que de el equipo, $2$ capitanes. Por un lado, es la misma que elegir primero los dos capitanes, y luego de completar todos los equipos con cada subconjunto de la otra $n-2$: $\binom{n}{2}2^{n-2}$

Por otro lado, este es el mismo para contar todos los equipos con 2 elementos, 3 elementos, los 4 elementos,..., $n$ elementos y, para cada una de las $k\in\{2,...,n\}$ seleccione los dos capitanes de ellos: $\binom{n}{k}\binom{k}{2}$. Por lo tanto, el total es de $\sum_{k=2}^n\binom{n}{k}\binom{k}{2}$

Ya que ambos procedements cuenta el mismo número de equipos, tenemos $\sum_{k=2}^{n}\binom{n}{k}\binom{k}{2}=\binom{n}{2}2^{n-2}$

Answer 3

$$\binom k2\binom nk=\dfrac{k(k-1)}2\cdot\dfrac{n(n-1)\cdot(n-2)!}{\{n-2-(k-2)\}!\cdot k(k-1)\cdot(k-2)!}=n(n-1)\binom{n-2}{k-2}$$ for $k \ ge2$

y$$\sum_{k=2}^n\binom{n-2}{k-2}=\sum_{r=0}^{n-2}\binom{n-2}r

se puede encontrar configurando$a=b=1$ en la expansión binomial de$$(a+b)^{n-2}