3
$\begingroup$

The identity is:

$$\sum_{k=0}^{m} (-1)^{k} {{n} \choose {k}}{{n-k}\choose{m-k}} = 0$$

I'm not even sure where to begin. Does anyone have any suggestions?

$\endgroup$
4
$\begingroup$

Let $A$ be an $n$-element set, and assume that $0<m\le n$; we’ll count the $m$-element subsets of $A$ that don’t contain any element of $A$ in two different ways. First, of course, it’s obvious that there are no such subsets. (This is why we have to take $m>0$: if $m=0$ there actually is one such subset, $\varnothing$.)

Now we’ll use inclusion-exclusion. As a first approximation there are $\binom{n}m$ $m$-subsets of $A$. Let $a\in A$ be arbitrary; there are $\binom{n-1}{m-1}$ $(m-1)$-subsets of $A\setminus\{a\}$, so there are $\binom{n-1}{m-1}$ $m$-subsets of $A$ that contain $a$. Since we want to count only those $m$-subsets of $A$ that don’t contain $a$, we need to subtract $\binom{n-1}{m-1}$. Moreover, we need to do this for each of the $\binom{n}1$ elements of $A$, so a second approximation to the desired number is

$$\binom{n}m-\binom{n}1\binom{n-1}{m-1}\;.\tag{1}$$

Now let $a$ and $b$ be distinct elements of $A$; every $m$-subset of $A$ that contains both $a$ and $b$ has been subtracted twice in $(1)$, once for $a$ and once for $b$, so we need to add these sets back in. There are $\binom{n-2}{m-2}$ ways to choose $m-2$ more elements of $A$ to expand $\{a,b\}$ to an $m$-subset of $A$, so there are $\binom{n-2}{m-2}$ $m$-subsets of $A$ that contain both $a$ and $b$. And there are $\binom{n}2$ possible pairs $\{a,b\}$ of distinct elements of $A$, so we have to add back $\binom{n-2}{m-2}$ for each of them, getting as a third approximation

$$\binom{n}m-\binom{n}1\binom{n-1}{m-1}+\binom{n}2\binom{n-2}{m-2}\;.$$

I expect that by now the full inclusion-exclusion argument is pretty clear.


By the way, there is also a combinatorial argument that doesn’t use inclusion-exclusion. Note first that

$$\binom{n}k\binom{n-k}{m-k}$$

is the number of ways to choose $k$ elements of $A$ and paint them red, and then choose $m-k$ of the remaining $n-k$ elements and paint them blue. It follows that

$$\sum_{k=0}^m\binom{n}k\binom{n-k}{m-k}\tag{2}$$

is simply the number of ways to choose $m$ elements of $A$, paint any subset of them red, and paint the remainder of the chosen elements blue. Let

$$\mathscr{P}=\{\langle S,R\rangle:S\text{ is an }m\text{-subset of }A\text{ and }R\subseteq S\}\;;$$

if you think of $R$ as the subset of $S$ that’s painted red (so that $S\setminus R$ is painted blue), it’s not hard to see that the sum in $(2)$ is simply $|\mathscr{P}|$. The sum

$$\sum_{k=0}^m(-1)^k\binom{n}k\binom{n-k}{m-k}\tag{3}$$

in a sense also counts $\mathscr{P}$, but it counts each $\langle S,R\rangle\in\mathscr{P}$ with a plus sign if $|R|$ is even and with a minus sign if $|R|$ is odd.

Let $S$ be any $m$-subset of $A$. Since $m>0$, $S$ has $2^{m-1}$ subsets of odd cardinality and $2^{m-1}$ subsets of even cardinality. Thus,

$$\sum_{R\subseteq S}(-1)^{|R|}=2^{m-1}-2^{m-1}=0\;,$$

and we see that $\{\langle S,R\rangle:R\subseteq S\}$ contributes $0$ to the sum in $(3)$. This is true for every $m$-subset $S$ of $A$, so the sum in $(3)$ must be $0$.

$\endgroup$
1
$\begingroup$

First see that the identity holds only when $m>0$. For $m=0$, L.H.S equates to $1$.


Proof by Double Counting

Q: Count the number of ways of selecting m red balls from a set of n blue balls and r red balls. Balls are distinct and numbered 1 to n and 1 to r respectively.

Answer 1: $r \choose m$

Answer 2: (By PIE)

Let $A_i$ is the number of selections of size m from the set of n blue and r red balls containing i-th blue ball.

Let Z denote the set of n blue balls and r red balls. Then, $A_\phi = {{n+r}\choose m}$ and $A_{I:|I|=k} = {{n+r-k}\choose{m-k}}$ and by the Principle of Exclusion-Inclusion,

The number of selections of size m containing only red balls from the set of n blue and r red balls = $$\sum_{k=0}^m {(-1)^k{n \choose k}{{n+r-k}\choose {m-k}}} $$

Now set $r=0$ to get,

$$\sum_{k=0}^m {(-1)^k{n \choose k}{{n-k}\choose {m-k}}} = {0 \choose m} = 0 $$ Since $m>0$.[Proved]

$\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.