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$
  • $\begingroup$ Have you considered how you might interpret the LHS with PIE? $\endgroup$ – Laars Helenius Dec 19 '16 at 2:44
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$
  • $\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$ – darij grinberg Dec 19 '16 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$ – Brian M. Scott Dec 20 '16 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$
  • $\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 '16 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$ – Markus Scheuer Dec 22 '16 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 '16 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.