probar e identificar combinatoriamente

Question

Probar la identidad:

(n-k) $\binom nk$ = n $\binom {n-1}k$

Lo he demostrado algebraicamente pero ahora necesito demostrarlo combinatoriamente ( contar algo de dos maneras).

Aquí está mi intento:

teorema: P(n,k) = $\frac {n!} {n-k!}$

teorema: C(n,k) = $\frac {n!} {k!(n-k)!}$

P(n,k) = C(n,k) * P(n-k,1)

P(n,K) = C(n,k) * $\frac {(n-k)!} {(n-k-1)!}$

P(n,K) = C(n,k) * $\frac {(n-k)(n-k-1)!} {(n-k-1)!}$

P(n,k) = c(n,k) * (n-k)

P(n,k) = $\frac {n!} {k!(n-k)!}$ * (n-k)

P(n,k) = (n-k)* $\binom nk$

^^ He probado una parte de la identidad,

pero no sé cómo demostrarlo de la otra manera: n $\binom {n-1}n$

¿alguna ayuda?

Answer 1

¿Cuántas maneras hay de elegir un conjunto de $j$ elementos de un conjunto de $n$ así como los elementos $1$ elemento especial del conjunto de $j$ ¿elementos?

Si elegimos el conjunto de $k$ elementos primero, hay $\binom{n}{j}$ conjuntos posibles y $j$ opciones para el elemento especial, por lo que el número de formas es $j\cdot\binom{n}{j}$ .

Si elegimos primero el elemento especial de entre los $n$ tenemos que elegir $j-1$ más de la $n-1$ elementos restantes para obtener la totalidad de $j$ -sujeción. Por lo tanto, el número de formas es $n\cdot \binom{n-1}{j-1}$ . Así que entonces $$j\cdot\binom{n}{n-j}=n\cdot\binom{n-1}{n-j}$$ Dejemos que $j=n-k$ para recuperar su identidad.