7
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Have you considered how you might interpret the LHS with PIE? $\endgroup$ Dec 19, 2016 at 2:44

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Note: You are assuming $y \geq x$. This assumption is legitimate (as a WLOG assumption) since your (reduced) identity is a polynomial identity in $y$; but this is worth mentioning explicitly. $\endgroup$ Dec 19, 2016 at 23:35
  • $\begingroup$ @darij: Aargh! Yes, of course. I have no idea what I was thinking. I’ll add suitable commentary in a bit. $\endgroup$ Dec 20, 2016 at 0:36
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Nice and compact Markus (+1)! by applying the Upper Negation twice you got same result as in my answer quicker. $\endgroup$
    – G Cab
    Dec 22, 2016 at 8:15
  • $\begingroup$ @GCab: Many thanks, GCab. Two aspects regarding your answer: It looks somewhat uncommon, that the equality chain starts and ends with the same expression. Maybe you could simply skip the leftmost expression. The last step in the equality chain is (for me) not that obvious. Maybe you could add a small comment to ease reading.Then your answer is for sure a good candidate for upvotes. Regards, $\endgroup$
    – epi163sqrt
    Dec 22, 2016 at 8:28
  • 1
    $\begingroup$ Thanks Markus, accept your suggestions. I tried and make more readable my answer. By the way, on this topic, I would like to know your opinion concerning answer to question 2064742 $\endgroup$
    – G Cab
    Dec 22, 2016 at 9:11
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .