Suma de los coeficientes binomiales $\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{2n - 2k}{n - 1} = 0$

Question

¿Cómo demostrar la siguiente identidad:

$$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{2n - 2k}{n - 1} = 0$$

Estoy tratando de usar la inclusión-exclusión, y esto se reduce a una suma como la inclusión-exclusión, y el $\binom{2n-2k}{n-1}$ plazo no importaría (será equivalente a los tamaños de los conjuntos). Esta es una manera correcta de ir?

Answer 1

De cuántas maneras se puede seleccionar $m\lt n$ plazas en una $2\times n$ bordo de esos que exactamente $n$ columnas contienen un seleccionado de la plaza?

[Modificar:]

De la falta de upvotes y el indagar el comentario de un distinguido usuario llego a la conclusión de que debo explicar esto tal vez demasiado lacónica respuesta.

El OP quería probar el resultado por la inclusión–exclusión. El número de formas de seleccionar $m$ plazas en una $2\times n$ bordo de esos que en la mayoría de las $j$ particular columnas contienen un seleccionado cuadrado es $\binom{2j}m$. Por medio de la inclusión–exclusión, si no se $a_j$ formas de hacer algo con en la mayoría de las $j$ objetos en particular, entonces hay

$$ \sum_{k=0}^n(-1)^k\binom nka_{n-k} $$

maneras de hacerlo con exactamente $n$ objetos (donde el coeficiente binomial cuenta el número de maneras de seleccionar los $n-k$ particulares de la $n$ objetos). Poner esto juntos se obtiene el número de formas de seleccionar $m$ plazas en una $2\times n$ bordo de esos que exactamente $n$ columnas contienen un seleccionado de la plaza:

$$ \sum_{k=0}^n(-1)^k\binom nk\binom{2n-2k}m\;. $$

Ya que es imposible tener exactamente $n$ columnas contienen un seleccionado plaza a menos de $n$ plazas son seleccionados, esto es$0$$m\lt n$, y por lo tanto, en particular, para $m=n-1$.

Answer 2

La función de $g:k\mapsto \binom{2n-2k}{n-1}$ es una función polinómica de grado $n-1$. La operación $f\mapsto\bigl(x\mapsto\sum_{k=0}^n(-1)^k\binom knf(x+k)\bigr)$ es igual a $(-1)^n\Delta^n$ donde $\Delta$ es el de las diferencias finitas operador $f\mapsto\bigl(x\mapsto f(x+1)-f(x)\bigr)$, que mata constante de las funciones y disminuye el grado de funciones polinómicas por $1$. Por lo tanto,$(-1)^n\Delta^n(g)=0$, lo que significa que $$ x\mapsto\sum_{k=0}^n(-1)^k\binom kng(x+k) $$ es la función cero. Aplicar ahora para $x=0$ obtener $$ 0=\sum_{k=0}^n(-1)^k\binom kng(k) = \sum_{k=0}^n(-1)^k\binom kn\binom{2n-2k}{n-1}. $$

Answer 3

Esto se puede hacer muy directa y podemos retener el dado rango del índice de $k.$ Supongamos que buscamos para evaluar $$\sum_{k=0}^n (-1)^k {n\choose k} {2n-2k\choose n-1}.$$

Introducir $${2n-2k\elegir n-1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n-2k}}{z^n} \; dz.$$

Esto da por la suma $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^n} \sum_{k=0}^n (-1)^k {n\elegir k} \frac{1}{(1+z)^{2k}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^n} \left(1-\frac{1}{(1+z)^2}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^n} (z^2+2z)^n \; dz = \frac{1}{2\pi i} \int_{|z|=\epsilon} (z+2)^n \; dz = 0.$$

Answer 4

Otra manera de hacer esto es utilizar el aceite de la serpiente. El uso de $m$ como una nueva variable libre (para $n - 1$), observe que fuera del rango dado el primer coeficiente binomial es cero, y escribir la generación de la función de la suma que queremos:

$\begin{align} \sum_{m \ge 0} z^m \sum_k (-1)^k \binom{n}{k} \binom{2 n - 2 k}{m} &= \sum_k (-1)^k \binom{n}{k} \sum_{m \ge 0} \binom{2 n - 2 k}{m} z^m \\ &= \sum_k (-1)^k \binom{n}{k} (1 + z)^{2 n - 2 k} \\ &= (1 + z)^{2 n} \sum_k (-1)^k \binom{n}{k} (1 + z)^{- 2 k} \\ &= (1 + z)^{2 n} \left(1 - (1 + z)^{-2}\right)^n \\ &= \left((1 + z)^2 - 1\right)^n \\ &= z^n (2 + z)^n \end{align}$

Ahora queremos que el coeficiente de $z^m$ de este:

$\begin{align} [z^m] z^n (2 + z)^n &= [z^{m - n}] (2 + z)^n \\ &= \binom{n}{m - n} 2^{n - (m - n)} \\ &= \binom{n}{m - n} 2^{2 n - m} \end{align}$

El problema original se pregunta por $m = n - 1$, bastante seguro, $\binom{n}{-1} = 0$.

Nota: El $[z^n]$ notación es descrito por Knuth como una manera más simple de manejar Egorychev del "método de los coeficientes", que creo que es lo que Marko Riedel está haciendo.