Proof of $\sum_{k=0}^m \binom{n}{k}(-1)^k = (-1)^m \binom{n-1}{m}$ for $n > m \geq 0$

Question

Let $n > m \geq 0$ be integers.

How can one prove the following equation?

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

According to our script we have to use the following: $(X \setminus \{ n \}) \cup (\{n\} \setminus X)$ and the following sets:

$G$ is the set of subsets $\{a_1,...,a_k\}$ of $[n]$ where $k \leq m$ is even.

$U$ is the set of subsets $\{a_1,...,a_k\}$ of $[n]$ where $k \leq m$ is odd.

I wasn't able to find a proof for this equation on stackexchange Math, nor was I able to find it on Google and I also don't know how to use the equation above to prove the following inequalities for an even $m$:

$$\sum_{j=1}^{m} (-1)^{j+1} \sum_{|I| = j} |A_I| \leq \left| \bigcup_{i=1}^n A_i \right| \leq \sum_{j=1}^{m+1} (-1)^{j+1} \sum_{|I| = j} |A_I|$$

Answer 1

As for the equation: This is a well-known fact which I think deserves a name ("alternating hockey-stick identity"?). I give three proofs in UMN Fall 2018 Math 5705 homework set #2 (Exercise 4).

As for the inequality: I assume that your $A_1, A_2, \ldots, A_n$ are $n$ finite sets, and that your $A_I$ means $\bigcap\limits_{i \in I} A_i$. Then, your inequality is the famous Bonferroni inequality. Let me give a hint to the proof. First of all, let $S = \bigcup\limits_{i \in I} A_i$ (so that all $A_i$ are subsets of $S$). Then, your inequality becomes \begin{equation} \sum_{j=0}^m \left(-1\right)^j \sum_{\left|I\right| = j} \left|A_I\right| \geq 0 \geq \sum_{j=0}^{m+1} \left(-1\right)^j \sum_{\left|I\right| = j} \left|A_I\right| \end{equation} (here, I have subtracted your inequality from $\left|S\right|$). In other words, you want to prove that for each nonnegative integer $k$, the number $\sum_{j=0}^k \left(-1\right)^j \sum_{\left|I\right| = j} \left|A_I\right|$ has the same sign as $\left(-1\right)^k$ (that is, it is nonnegative when $k$ is even, and it is nonpositive when $k$ is odd). To do so, let us define one more notation: For each $s \in S$, let $c\left(s\right)$ denote the number of $i \in \left\{1,2,\ldots,n\right\}$ satisfying $s \in A_i$ (in other words, it counts how many of your sets contain $s$). Then, \begin{equation} \sum_{j=0}^m \left(-1\right)^j \sum_{\left|I\right| = j} \left|A_I\right| = \sum_{\left|I\right| \leq m} \left(-1\right)^{\left|I\right|} \left|A_I\right| = \left(-1\right)^m \sum_{s \in S} \dbinom{c\left(s\right) - 1}{m} \end{equation} (by Theorem 3.45 in my Notes on the combinatorial fundamentals of algebra, version of 10th of January 2019, but you can prove this yourself -- this is where the preceding equation is helpful). The right hand side of this equality has the same sign as $\left(-1\right)^m$, because each of the binomial coefficients $\dbinom{c\left(s\right) - 1}{m}$ is nonnegative (indeed, each $s \in S$ satisfies $c\left(s\right) \geq 1$ and thus $c\left(s\right) - 1 \geq 0$). Hence, the left hand side must have the same sign as $\left(-1\right)^m$ as well. This proves the claim. Let me know if you need more hints.

Answer 2

$$\displaystyle \sum^{m}_{k=0}(-1)^{k}\cdot \binom{n}{k}=$$

Coeff. of $x^{m}$ in

$$\bigg[\binom{n}{0}-\binom{n}{1}x+\cdots +(-1)^n\binom{n}{n}x^n \bigg](x^m+x^{m-1}+x^{m-2}+\cdots +x+1).$$

Coeff. of $x^{m}$ in $\displaystyle (1-x)^n\cdot \bigg(\frac{1-x^{m+1}}{1-x}\bigg).$

Coeff. of $x^{m}$ in $(1-x)^{n-1}\cdot (1-x^{m+1}).$

So coeff. of $x^{m}$ in $(1-x)^{n-1}$ is $ \displaystyle = (-1)^{m}\cdot \binom{n-1}{m}.$

Answer 3

Rewrite $\binom nk$ to $\binom{n-1}{k-1}+\binom{n-1}k$, and your sum will telescope.

Answer 4

Answer based on your hint: Suppose that a subset $X$ of $[n]=\{1,2,\ldots,n\}$ is given. Then for each $X$, we can define $X'$ as $X' = X\cup\{n\}$ if $n\notin X$ or $X'=X\setminus \{n\}$ if $n\in X$. Note that $(X')'=X$ and thus $(X,X')$ partitions the family of all subsets of $[n]$. We denote $S'=\{X'\;|\;X\in S\}$.

Now, the given equation is equivalent to $$ \sum_{j\text{ even},j\le m}\binom{n}{j}-\sum_{j\text{ odd},j\le m}\binom{n}{j}=|I_1|-|I_2|=(-1)^m \binom{n-1}{m}. $$ Let $I_1$ denotes the set of all $X$ for which $|X|$ is even and $\le m$ and $I_2$ the set of all $Y$ for which $|Y|$ is odd and $\le m$. We denote by $X$ the member of $I_1$ and by $Y$ that of $I_2$. Since $|I_1|$ is the number of $X$'s, we can count it by counting the corresponding $X'\in I_1'$. We can see that $|X'|$ and $|X|$ are different only by $1$, and hence $|X'|$ is odd. Now, suppose that $m$ is odd. Then, since $|X|<m$ (cannot be equal), it holds that $|X'|\le m$. So $I_2$ contains $I_1'$ and $|I_1|-|I_2|=-|I_2\setminus I_1'|$ corresponds to $(-1)$ times the number of $Y$ such that $Y\ne X'$ for all $X$. Since $Y'\ne X''=X$ for all $X\in I_1$, it is equivalent to $|Y'|=|Y|+1=m+1$ and it follows that $n\notin Y$ and $|Y|=m$. The number of such $Y$ is $\binom{n-1}{m}$ and this shows $|I_1|-|I_2| = -\binom{n-1}{m}$.
Conversely, suppose $m$ is even. Then, since $|Y|<m$, we must have $|Y'|\le m$. This shows $I_1$ contains $I_2'$. And the difference $I_1\setminus I_2'$ is the set of all $X$ for which $X\ne Y'$ for all $Y$. This is equivalent to $|X'|=|X|+1=m+1$, i.e. $|X|=m$ and $n\notin X$. The number of such $X$ is equal to $\binom{n-1}{m}$ and hence this proves $|I_1|-|I_2| =|I_1\setminus I_2'|= \binom{n-1}{m}$ for even $m$ case.

Answer 5

There is a nice combinatorial proof of this identity using a sign-reversing involution. You summation counts subsets of $\{1,2,\dots,n\}$ of size $m$ or fewer, except subsets with even size are counted positively and those with odd size are counted negatively.

For each set $S$ which does not contain $1$, pair it with the set $S\cup \{1\}$. Note that the sizes of $S$ and $S\cup \{1\}$ have opposite parities, so they cancel each other in your sum and can be ignored.

Which sets are not paired with anything? The only reason $S\cup \{1\}$ would not exist was if $|S|=m$, in which case $S\cup \{1\}$ would be too big and would not be counted. Therefore, the number of unpaired sets is $\binom{n-1}m$, and these sets all have parity $(-1)^m$ in your sum, so the sum is $(-1)^m\binom{n-1}m$.

---

To prove your inequalities, consider the number of times a particular element $x$ is counted in the sum $\sum_{j=1}^m (-1)^{j+1} \sum_{|I|=j} |A_i|$. Suppose $x$ is contained in $k$ of the sets, $A_i$. As long a $j\le m$, there are $\binom{k}{j}$ ways to choose $I$ so that $|I|\le m$ and $x\in A_I$. Therefore, the element $x$ is counted $$ \sum_{j=1}^{\min(k,m)}(-1)^{j+1}\binom{k}{j}=\binom{k}0+\sum_{j=0}^{\min(k,m)}(-1)^{j+1}\binom{k}{j}=1-(-1)^{\min(k,m)}\binom{k-1}{\min(k,m)} $$ Note that if $k=0$, then $x$ is counted $1-(-1)^0\binom{-1}0=0$ times. This is the correct number, since $k=0$ implies $x$ is not in the union of the $A_i$. If $m\ge k>0$, then $x$ is counted once in $\bigcup_i A_i$, so $1-(-1)^k\binom{k-1}{k}=0$ is the correct count for $x$. Otherwise, we have $k>0$ and $k>m$, in which case $x$ is counted once, so $1-(-1)^{m}\binom{k-1}{m} $ is either an overestimate or underestimate for the count of $x$, depending on the parity of $m$.