Demostrando la identidad del coeficiente binomial usando la función generadora

Usamos el coeficiente del operador$[z^n]$para denotar el coeficiente de una serie. De esta manera podemos escribir por ejemplo

Obtenemos

$$\begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{ (-1)^k \binom{n}{k} \binom{nx-kx}{n+1}}\\ &=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}\binom{kx}{n+1}\tag{2}\\ &=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}[z^{n+1}](1+z)^{kx}\tag{3}\\ &=[z^{n+1}]\left(\left(1+z\right)^x-1\right)^n\tag{4}\\ &=[z^{n+1}]\left(\sum_{j=1}^x\binom{x}{j}z^j\right)^n\tag{5}\\ &=[z]\left(\sum_{j=0}^{x-1}\binom{x}{j+1}z^j\right)^n\tag{6}\\ &\,\,\color{blue}{=nx^{n-1}\binom{x}{2}}\tag{7} \end{align*}$$ y sigue la demanda.

Comentario:

• En (2) cambiamos el orden de la suma$k\to n-k$.

• En (3) aplicamos el coeficiente de operador según (1).

• En (4) usamos la linealidad del coeficiente del operador y aplicamos el teorema del binomio.

• En (5) aplicamos de nuevo el teorema del binomio.

• En (6) cambiamos el índice para comenzar con$j=0$y factorizar$z^n$aplicando la regla$[z^p]z^qA(z)=[z^{p-q}]A(z)$.

• En (7) notamos que para seleccionar el coeficiente de$z$en (6) tenemos que tomar$j=1$una vez y$j=0$para el otro$(n-1)$factores esto lo hacemos$n$veces.

Aquí hay una prueba combinatoria simple.

Imagina un$n\times x$cuadrícula de objetos. Ambos lados de la ecuación son respuestas a la pregunta "¿Cuántas formas hay de seleccionar$n+1$objetos de esta cuadrícula para que cada uno tenga al menos un objeto seleccionado?"

Por un lado,$\sum_{k=0}^n (-1)^k \binom{n}{k} \binom{nx-kx}{n+1}$responde a esta pregunta utilizando el principio de inclusión-exclusión. Tomalo todo$\binom{nx}{n+1}$formas de seleccionar$n+1$objetos de la cuadrícula, luego para cada fila, reste el$\binom{nx-x}{n+1}$selecciones que pierden esa fila. Luego vuelve a sumar, para cada par de filas, el$\binom{nx-2x}{n+1}$selecciones que pierden ambas filas, y así sucesivamente.

Por otro lado, si se cubren todas las filas, entonces debe existir exactamente una fila con dos objetos seleccionados, mientras que cada otra fila tiene exactamente un objeto seleccionado. Hay$n$formas de elegir la fila con dos objetos seleccionados,$\binom x2$maneras de elegir los dos objetos de esa fila, entonces$x^{n-1}$formas de seleccionar los objetos de las filas restantes.