Prove that $\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

I need to prove this equation $$\sum_{k=0}^n (-1)^k\frac{{ {n}\choose{k}}{ {x}\choose{k}}}{{ {y}\choose{k}}} = \frac{{ {y-x}\choose{n}}}{{ {y}\choose{n}}}$$

where $x$, $y$ and $n$ are nonnegative integers satisfying $y \geq n$.

The sign $(-1)^k$ suggests using binomial expansion, I've tried this, but without success. Is there a better way?

Answer 1

Note that

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

so

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

and after multiplication by $\binom{y}n$, the proposed identity reduces to

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

$\binom{y-x}n$ is the number of $n$-element subsets of $[y]\setminus[x]$, where as usual $[x]=\{1,\ldots,x\}$. For $k\in[x]$ let $\mathscr{A}_k$ be the family of $n$-element subsets of $[y]$ that contain $k$. Then

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

whenever $\varnothing\ne I\subseteq[x]$, so by the inclusion-exclusion principle we have

$$\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*}$$

assuming that $x\ge n$. (Recall that by definition $\binom{y-k}{n-k}=0$ when $n-k<0$.) This is the number of $n$-element subsets of $[y]$ that do intersect $[x]$, so

$$\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*}$$

as desired.

Added: as darij grinberg pointed out in the comments, the combinatorial interpretation requires the assumption that $y\ge x$. For each $x$ the combinatorial argument establishes $(1)$ for each integer $y\ge x$ and each side of $(1)$ is an $n$-th degree polynomial in $y$, so $(1)$ must be a polynomial identity.

Answer 2

Standing the conditions you gave, the $y \choose n$ is not null, and we can multiply by it both sides, giving $$ \left( \begin{gathered} y - x \\ n \\ \end{gathered} \right) = \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {\left( { - 1} \right)^{\,k} \left( \begin{gathered} y \\ n \\ \end{gathered} \right)\left( \begin{gathered} n \\ k \\ \end{gathered} \right)\left( \begin{gathered} x \\ k \\ \end{gathered} \right)/\left( \begin{gathered} y \\ k \\ \end{gathered} \right)} $$ The RHS can be developed as

$$ \begin{gathered} \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {\left( { - 1} \right)^{\,k} \left( \begin{gathered} y \\ n \\ \end{gathered} \right)\left( \begin{gathered} n \\ k \\ \end{gathered} \right)\left( \begin{gathered} x \\ k \\ \end{gathered} \right)/\left( \begin{gathered} y \\ k \\ \end{gathered} \right)} = \hfill \\ = \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {\left( { - 1} \right)^{\,k} \left( \begin{gathered} y \\ k \\ \end{gathered} \right)\left( \begin{gathered} y - k \\ n - k \\ \end{gathered} \right)\left( \begin{gathered} x \\ k \\ \end{gathered} \right)/\left( \begin{gathered} y \\ k \\ \end{gathered} \right)} = \hfill \\ = \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {\left( { - 1} \right)^{\,k} \left( \begin{gathered} y - k \\ n - k \\ \end{gathered} \right)\left( \begin{gathered} x \\ k \\ \end{gathered} \right)} = \hfill \\ = \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {\left( \begin{gathered} y - k \\ n - k \\ \end{gathered} \right)\left( \begin{gathered} k - x - 1 \\ k \\ \end{gathered} \right)} = \hfill \\ = \left( \begin{gathered} y - x \\ n \\ \end{gathered} \right) \hfill \\ \end{gathered} $$ which is valid for $x$ and $y$ even complex, with the only condition that ${y \choose n }\ne 0$.

• ---Note ----*

1st step) Trinomial Revision :
$\left( \begin{gathered} y \\ n \\ \end{gathered} \right)\left( \begin{gathered} n \\ k \\ \end{gathered} \right) = \left( \begin{gathered} y \\ k \\ \end{gathered} \right)\left( \begin{gathered} y - k \\ n - k \\ \end{gathered} \right)$

2nd step) simplifying $ {y \choose k }$

3rd step) VanderMonde Convolution

Answer 3

Here is a variation based upon Vandermonde's identity. It is convenient to simplify OPs identity \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*}

by multiplying both sides with $\binom{y}{n}$ and

we claim

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

We obtain \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*} and the claim follows.

Comment:

• In (1) we apply to $\binom{y-k}{n-k}$ the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$

• In (2) we apply Vandermonde's identity to the right-hand series in (1)

• In (3) we apply the binomial identity from (1) to $\binom{x+n-y-1}{n}$