Ayuda con el binomio identidad

Question

En mi trabajo, me llevó a la siguiente identidad. Agradecería si alguien pudiera proporcionar una fácil prueba.

Supongamos $n, d, k \in \mathbb{Z}$, e $d \geq 0$.

$$ \sum_{j = 0}^d (-1)^{d-j} \cdot \binom{d}{k} \cdot \binom{n-j-1}{n-d-1} \cdot \binom{n-d}{j-k} = \left\{ \begin{array}{ll} 0 & : d \neq k\\ 0 & : n < 0\\ 1 & : 0 \leq n \leq d\\ 2 & : d < n \end{array} \right. $$

Yo he ido a la página de la wikipedia sobre los coeficientes binomiales, buscando útil identidades a aplicar. https://en.wikipedia.org/wiki/Binomial_coefficient

Muchos conocidos identidades parece aplicable, pero no sé cómo manejar la forma en que $j$ aparece una vez en la parte superior de uno de los coeficientes binomiales, y una vez en la parte inferior. La identidad

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

tiene el movimiento de la variable en ambos lugares, pero no veo cómo utilizar este.

Lo que estoy tratando de evitar que la prueba es por inducción. El contexto es, necesito esta identidad para un ejemplo en un papel. No quiero quedar atascado en el ejemplo, pero me gustaría incluir una prueba plena.

Answer 1

Sustituto $r=d-j$ y el uso de la parte superior de la negación seguida de Vandermonde de la Identidad: $$\requieren{cancel}\begin{align}\sum_{j=0}^d(-1)^{d-j}\binom{d}{k} \binom{n-j-1}{n-d-1} \binom{n-d}{j-k} &=\binom dk \sum_{r=0}^d(-1)^r\color{blue}{\binom{n-d-1+r}{n-d-1}}\binom{n-d}{d-k-r}\\ &=\binom dk \sum_{r=0}^d(-1)^r\color{blue}{\binom{n-d-1+r}r}\binom{n-d}{d-k-r}\\ &=\binom dk \sum_{r=0}^d(-1)^r\color{blue}{\binom{d-n}r(-1)^r}\binom{n-d}{d-k-r}\\ &=\binom dk \sum_{r=0}^d\binom{d-n}r\binom{n-d}{d-k-r}\\ &=\binom dk \binom 0{d-k}\\ &=\begin{cases}1\quad \text{if}\quad d=k \\0\quad \text{otherwise}\end{casos} \end{align}\qquad$$ como $$\binom 0{d-k}=\begin{cases}1\quad \text{for}\quad d-k=0\\ 0\quad\text{otherwise}\end{cases}$$

Answer 2

Cálculo con valores pequeños de a $n,d,k\geq 0$ se muestra en el siguiente es válido

\begin{align*} \sum_{j=0}^{d}(-1)^{d-j}\binom{d}{k}\binom{n-j-1}{n-d-1}\binom{n-d}{j-k} = \begin{cases} 1&\qquad 0\leq k=d<n\\ 0&\qquad \text{otherwise} \end{casos} \etiqueta{1} \end{align*}

Nota: Es fácil demostrar el caso especial $k=d<n$. Con el fin de mostrar que la expresión es cero, de lo contrario, utilizamos las técnicas conocidas como formal residual cálculo de potencia de la serie. Se basan en la Cauchys teorema de los residuos y fueron introducidos por el G. P. Egorychev (Representación Integral y el Cálculo de la Combinatoria Sumas) para calcular el binomio identica.

Empezamos con la más fácil

Caso: $0\leq k=d<n$

Si $k=d$ obtenemos

\begin{align*} \sum_{j=0}^{d}&(-1)^{d-j}\binom{d}{k}\binom{n-j-1}{n-d-1}\binom{n-d}{j-k}\tag{2}\\ &=\sum_{j=k}^{d}(-1)^{d-j}\binom{d}{k}\binom{n-j-1}{n-d-1}\binom{n-d}{j-k}\\ &=(-1)^{d-d}\binom{d}{d}\binom{n-d-1}{n-d-1}\binom{n-d}{0}\\ &=1 \end{align*}

Esto prueba la primera parte de (1).

Recordemos que un coeficiente binomial $\binom{n}{k}$ es cero si $k<0$ o $n<k$. Observamos en (2) el índice de $j$ de los de más a la derecha coeficiente binomial $\binom{n-d}{j-k}$tiene que ser mayor o igual $k$ lo contrario, el sumando contribuye a cero. Así, el límite inferior del índice de $j$$k$.

También observamos que el coeficiente binomial $\binom{n-d-1}{n-d-1}$ es igual a $1$ sólo en el caso de $n-d-1\geq 0$, lo que significa $d$ menos de $n$ y la parte fácil de (1) se muestra.

También vemos que el $\binom{d}{k}$ es cero si $d$ es de menos de $k$. Así, el único caso que sigue es

Caso: $0\leq k<d$

Utilizamos el residuo de la notación y escribir, por ejemplo, \begin{align*} \mathop{res}_z\frac{(1+z)^{n}}{z^{k+1}}=\frac{1}{2\pi i}\oint_{|z|=1}\frac{(1+z)^{n}}{z^{k+1}}\mathop{dz}\tag{3} =[z^k](1+z)^n=\binom{n}{k} \end{align*}

De hecho vamos a utilizar sólo dos aspectos de esta teoría:

Deje $A(z)=\sum_{j=0}^{\infty}a_jz^j$ ser un poder formal de la serie, a continuación,

• Escribir el binomio coeffients como residuos de la correspondiente poder formal de la serie

\begin{align*} \mathop{res}_{z}\frac{A(z)}{z^{j+1}}=a_j\tag{4} \end{align*}

• Aplicar la norma de sustitución para poder formal de la serie:

\begin{align*} A(z)=\sum_{j=0}^{\infty}a_jz^{j}=\sum_{j=0}^{\infty}z^j\mathop{res}_{w}\frac{A(w)}{w^{j+1}}\tag{5} \end{align*}

\begin{align*} \binom{d}{k}\sum_{j=k}^{d}&(-1)^{d-j}\binom{n-j-1}{n-d-1}\binom{n-d}{j-k}\tag{6}\\ &=\binom{d}{k}\sum_{j=0}^{\infty}(-1)^{d-j}\mathop{res}_{z}\frac{(1+z)^{n-j-1}}{z^{n-d}} \mathop{res}_{u}\frac{(1+u)^{n-d}}{u^{j-k+1}}\tag{7}\\ &=(-1)^d\binom{d}{k}\mathop{res}_{z}\frac{(1+z)^{n-1}}{z^{n-d}} \sum_{j=0}^{\infty}\left(\frac{-1}{1+z}\right)^j \mathop{res}_u\frac{(1+u)^{n-d}u^k}{u^{j+1}}\tag{8}\\ &=(-1)^d\binom{d}{k}\mathop{res}_{z}\frac{(1+z)^{n-1}}{z^{n-d}} \left(1-\frac{1}{1+z}\right)^{n-d}\left(\frac{-1}{1+z}\right)^k\tag{9}\\ &=(-1)^{d+k}\binom{d}{k}\mathop{res}_{z}(1+z)^{d-k-1}\\ &=(-1)^{d+k}\binom{d}{k}[z^{-1}](1+z)^{d-k-1}\tag{10}\\ &=0 \end{align*}

Desde $(1+z)^{d-k-1}$ no tiene un valor distinto de cero poder de $z^{-1}$, la expresión (10) es igual a cero. Esto demuestra la segunda parte de (1)

Comentario:

• En (7) se amplía el límite superior de la suma sin cambiar el valor ya que son sólo la adición de ceros y nos re-escribir los coeficientes binomiales el uso de los residuos de acuerdo a (3) y (4)

• En (8) hacemos algunos reordenamientos para prepararse para la sustitución de la regla

• En (9) aplicamos la sustitución de la regla de acuerdo a (5)