Hermoso identidad: $\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$

Question

Vamos a m $n\ge 0$ ser de dos números enteros. Demostrar que

$$\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$$

donde $\delta_{mn}$ representa la delta de Kronecker (definido por $\delta_{mn} = \begin{casos} 1, & \text{si } m=n; \\ 0, & \text{si } m\neq n \end{casos}$).

Nota: he puesto la etiqueta de "álgebra lineal", porque pienso que es una forma elegante para atacar el problema de utilizar un determinado tipo de matrices.

Espero que usted disfrute. :)

Answer 1

Esto se deduce fácilmente de la Multinomial Teorema, creo.

$$ 1 = 1^n = (1 - x + x)^n$$ $$ = \sum_{a+b+c=n} {n \elegir a,b,c} 1^a \cdot (-x)^b \cdot x^c$$ $$ = \sum_{m=0}^{n} \sum_{k=m}^{n} {n \elegir m,k-m,n-k} 1^{m} \cdot (-x)^{k-m} \cdot x^{n-k} $$ $$ = \sum_{m=0}^{n} \left[ \sum_{k=m}^{n} (-1)^{k-m} {k \elegir m}{n \elegir k} \right] x^{n-m}$$

La comparación de los coeficientes de ahora da el resultado inmediatamente.

Answer 2

El espacio vectorial de los polinomios en una variable tiene dos bases $\{1, x, x^2, ... \}$ y $\{1, (x+1), (x+1)^2, ... \}$ y yo creo que lo que has escrito es equivalente a la afirmación de que el cambio de base de las matrices entre estas dos bases de multiplicar a la identidad.

Todavía estoy pensando en la inclusión-exclusión en el argumento.

Answer 3

He aquí otra manera de mirar Aryabhata de la prueba: la suma de los recuentos de todas las particiones de $[n]$ en tres sets $A,B,C$ satisfacer $|C|=m$, ponderada en función $(-1)^{|A|}$. La identidad sólo dice que si $n \neq m$, el número de particiones con $||$ incluso es el mismo que con $||$ impar.

El último hecho se demuestra por el siguiente cartel-el cambio de la involución: selecciona el primer elemento que no está en $C$ (debe ser uno desde $n \neq m$), y la vuelta de $a$ a $B$ o viceversa.

Answer 4

Esto también se desprende directamente de la trinomio revisión formula $\binom{r}{m} \binom{m}{k} = \binom{r}{k} \binom{r-k}{m-k}$, que es fácilmente demostrado por escrito los coeficientes binomiales en factorial forma y reagrupación. (Véase, por ejemplo, el Concreto de las Matemáticas, 2ª ed., p. 168.)

Tenemos $$\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \sum_{k=m}^n (-1)^{k-m} \binom{n}{m} \binom{n-m}{k-m} = \binom{n}{m} \sum_{k=0}^{n-m} (-1)^k \binom{n-m}{k}$$ $$= \binom{n}{m} (1 - 1)^{n-m} [n \ge m] = \binom{n}{m} \delta_{mn} = \delta_{mn}.$$

Answer 5

También puede utilizar la siguiente fórmula para el cálculo finito alternando binomial se transforma. Deje que $B(f(k),n)$ denotar la alternancia de binomio de transformación; es decir, $$B(f(k),n) = \sum_{k=0}^n (-1)^k \binom{n}{k} f(k).$$ Entonces (la fórmula) $A$B(f(k),n) = -B(\Delta f(k),n-1) + f(0)[n=0].$$ (Aquí, $\Delta f(k)$ es la diferencia finita $f(k+1) - f(k)$, y la expresión $[n=0]$ evalúa a $1$ si $n = 0$ y $0$ lo contrario. También, tenga en cuenta que el primer argumento a $B$ es una función, mientras que el segundo es un número).

A partir de $f(k) = 1$, tenemos $\Delta f(k) = 0$. Desde $B(0,n-1)$ claramente $0$, $B(1,n) = [n=0]$. El último es sólo la conocida fórmula $$\sum_{k=0}^n (-1)^k \binom{n}{k} = [n=0].$$

Luego, continuando a tomar antidifferences, y usando la notación $k^{\underline{m}}$ para la caída de los factorial $k(k-1)\cdots (k-m+1)$ así como el poder de la regla de las diferencias finitas, $\Delta k^{\underline{m}} = m k^{\underline{m-1}}$, tenemos

$$\sum_{k=0}^n (-1)^k \binom{n}{k}k = -B(1,n-1) = - [n-1=0] = -[n=1],$$ $$\sum_{k=0}^n (-1)^k \binom{n}{k} k^{\underline{2}} = -2B(k,n-1) = 2 [(n-1) = 1] = 2[n=2],$$ $$\sum_{k=0}^n (-1)^k \binom{n}{k} k^{\underline{3}} = -3B(k^{\underline{2}},n-1) = -6[n-1 = 2] = -6[n=3],$$ y así sucesivamente, hasta llegar a la $$\sum_{k=0}^n (-1)^k \binom{n}{k} k^{\underline{m}} = -mB(k^{\underline{m-1}},n-1) = (-1)^m m![n=m].$$

Desde $k(k-1)\cdots (k-m+1) = \frac{k!}{(k-m)!}$, dividir ambos lados de esta última identidad por $(-1)^m m!$ demuestra el OP de la identidad.

(El cálculo finito fórmula para la alternancia binomio transforma y este argumento son un extracto de mi artículo "Combinatoria sumas y diferencias finitas," Matemáticas Discretas 307 (24): 3130-3146, 2007.)