Pruebalo $\sum_{k=0}^n (-1)^k\frac{{ {n}\choose{k}}{ {x}\choose{k}}}{{ {y}\choose{k}}} = \frac{{ {y-x}\choose{n}}}{{ {y}\choose{n}}}$

Question

Es necesario demostrar esta ecuación %#% $ #%

donde $$\sum_{k=0}^n (-1)^k\frac{{ {n}\choose{k}}{ {x}\choose{k}}}{{ {y}\choose{k}}} = \frac{{ {y-x}\choose{n}}}{{ {y}\choose{n}}}$, $x$ y $y$ son números enteros no negativos satisfacción $n$.

El signo $y \geq n$ sugiere usando la expansión binomial, he intentado esto, pero sin éxito. ¿Hay una manera mejor?

Answer 1

Tenga en cuenta que

$$\binom{y}n\binom{n}k=\binom{y}k\binom{y-k}{n-k}\;,$$

así

$$\binom{y}n\cdot\frac{\binom{n}k\binom{x}k}{\binom{y}k}=\binom{y-k}{n-k}\binom{x}k\;,$$

y después de la multiplicación por $\binom{y}n$, la propuesta de la identidad se reduce a

$$\sum_{k=0}^n(-1)^k\binom{x}k\binom{y-k}{n-k}=\binom{y-x}n\;.\tag{1}$$

$\binom{y-x}n$ es el número de $n$-elemento de subconjuntos de a $[y]\setminus[x]$, donde como de costumbre,$[x]=\{1,\ldots,x\}$. Para $k\in[x]$ deje $\mathscr{A}_k$ ser parte de la familia de $n$-elemento de subconjuntos de a $[y]$ que contengan $k$. Entonces

$$\left|\,\bigcap_{k\in I}\mathscr{A}_k\,\right|=\binom{y-|I|}{n-|I|}$$

siempre que $\varnothing\ne I\subseteq[x]$, así también por la inclusión-exclusión en el principio de que tenemos

$$\begin{align*} \left|\,\bigcup_{k\in[x]}\mathscr{A}_k\,\right|&=\sum_{\varnothing\ne I\subseteq[x]}(-1)^{|I|+1}\binom{y-|I|}{n-|I|}\\ &=\sum_{k=1}^x(-1)^{k+1}\binom{x}k\binom{y-k}{n-k}\\ &=\sum_{k=1}^n(-1)^{k+1}\binom{x}k\binom{y-k}{n-k}\;, \end{align*}$$

suponiendo que $x\ge n$. (Recordemos que, por definición, $\binom{y-k}{n-k}=0$ al $n-k<0$.) Este es el número de $n$-elemento de subconjuntos de a $[y]$ que hacer cruzan $[x]$, por lo que

$$\begin{align*}\binom{y-x}n&=\binom{y}n-\left|\,\bigcup_{k\in[x]}\mathscr{A}_k\,\right|\\ &=\binom{y}n-\sum_{k=1}^n(-1)^{k+1}\binom{x}k\binom{y-k}{n-k}\\ &=\binom{y}n+\sum_{k=1}^n(-1)^k\binom{x}k\binom{y-k}{n-k}\\ &=\sum_{k=0}^n(-1)^k\binom{x}k\binom{y-k}{n-k}\;, \end{align*}$$

como se desee.

Agregado: como darij grinberg se señaló en los comentarios, la combinatoria interpretación requiere la suposición de que $y\ge x$. Para cada una de las $x$ la combinatoria argumento establece $(1)$ para cada entero$y\ge x$, y a cada lado de la $(1)$ $n$- ésimo polinomio de grado en $y$, lo $(1)$ debe ser un polinomio de identidad.

Answer 2

Permanente de las condiciones que dieron, el $y \choose n$ no es nulo, podemos multiplicar por ambos lados, dando $$ \left( \begin{gathered} y - x \\ n \\ \end{reunieron} \right) = \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {\left( { - 1} \right)^{\,k} \left( \begin{gathered} y \\ n \\ \end{reunieron} \right)\left( \begin{gathered} n \\ k \\ \end{reunieron} \right)\left( \begin{gathered} x \\ k \\ \end{reunieron} \right)/\left( \begin{gathered} y \\ k \\ \end{reunieron} \right)} $$ La CARTA puede ser desarrollado como

$$ \begin{gathered} \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {\left( { - 1} \right)^{\,k} \left( \begin{gathered} y \\ n \\ \end{reunieron} \right)\left( \begin{gathered} n \\ k \\ \end{reunieron} \right)\left( \begin{gathered} x \\ k \\ \end{reunieron} \right)/\left( \begin{gathered} y \\ k \\ \end{reunieron} \right)} = \hfill \\ = \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {\left( { - 1} \right)^{\,k} \left( \begin{gathered} y \\ k \\ \end{reunieron} \right)\left( \begin{gathered} y - k \\ n - k \\ \end{reunieron} \right)\left( \begin{gathered} x \\ k \\ \end{reunieron} \right)/\left( \begin{gathered} y \\ k \\ \end{reunieron} \right)} = \hfill \\ = \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {\left( { - 1} \right)^{\,k} \left( \begin{gathered} y - k \\ n - k \\ \end{reunieron} \right)\left( \begin{gathered} x \\ k \\ \end{reunieron} \right)} = \hfill \\ = \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {\left( \begin{gathered} y - k \\ n - k \\ \end{reunieron} \right)\left( \begin{gathered} k - x - 1 \\ k \\ \end{reunieron} \right)} = \hfill \\ = \left( \begin{gathered} y - x \\ n \\ \end{reunieron} \right) \hfill \\ \end{se reunieron} $$ lo que es válido para $x$ $y$ más complejas, con la única condición de que ${y \choose n }\ne 0$.

• ---Nota \begin{gathered} y \\ n \\ \end*

1er paso) Trinomio de Revisión :
$\left( \begin{gathered} n \\ k \\ \end{reunieron} \right)\left( \begin{gathered} y \\ k \\ \end{reunieron} \right) = \left( \begin{gathered} y - k \\ n - k \\ \end{reunieron} \right)\left( -#-#-{reunieron} \right)$

2º paso) simplificar $ {y \choose k }$

3er paso) VanderMonde de Convolución

Answer 3

Aquí es una variación sobre la basa de Vandermonde de la identidad. Es conveniente simplificar la OPs identidad \begin{align*} \sum_{k=0}^n (-1)^k\frac{{ {n}\choose{k}}{ {x}\choose{k}}}{{ {y}\choose{k}}} = \frac{{ {y-x}\choose{n}}}{{ {y}\choose{n}}} \end{align*}

al multiplicar ambos lados con $\binom{y}{n}$ y

pretendemos

\begin{align*} \sum_{k=0}^n(-1)^k\binom{x}{k}\binom{y-k}{n-k}=\binom{y-x}{n} \end{align*}

Obtenemos \begin{align*} \sum_{k=0}^n(-1)^k\binom{x}{k}\binom{y-k}{n-k}&=(-1)^n\sum_{k=0}^n\binom{x}{k}\binom{n-y-1}{n-k}\tag{1}\\ &=(-1)^n\binom{x+n-y-1}{n}\tag{2}\\ &=\binom{y-x}{n}\tag{3} \end{align*} y el reclamo de la siguiente manera.

Comentario:

• En (1) se aplican a $\binom{y-k}{n-k}$ el binomio identidad $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$

• En (2) aplicamos Vandermonde de la identidad a la mano derecha de la serie en (1)

• En (3) se aplica el binomio identidad de (1) a $\binom{x+n-y-1}{n}$