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

Mathematics Asked by NotEinstein on January 1, 2022

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

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 $$Scup {1}$$. Note that the sizes of $$S$$ and $$Scup {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 $$Scup {1}$$ would not exist was if $$|S|=m$$, in which case $$Scup {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)^mbinom{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 $$jle m$$, there are $$binom{k}{j}$$ ways to choose $$I$$ so that $$|I|le m$$ and $$xin 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)^0binom{-1}0=0$$ times. This is the correct number, since $$k=0$$ implies $$x$$ is not in the union of the $$A_i$$. If $$mge k>0$$, then $$x$$ is counted once in $$bigcup_i A_i$$, so $$1-(-1)^kbinom{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$$.

Answered by Mike Earnest on January 1, 2022

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 $$bigcaplimits_{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 = bigcuplimits_{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(-1right)^j sum_{left|Iright| = j} left|A_Iright| geq 0 geq sum_{j=0}^{m+1} left(-1right)^j sum_{left|Iright| = j} left|A_Iright| end{equation}$$ (here, I have subtracted your inequality from $$left|Sright|$$). In other words, you want to prove that for each nonnegative integer $$k$$, the number $$sum_{j=0}^k left(-1right)^j sum_{left|Iright| = j} left|A_Iright|$$ has the same sign as $$left(-1right)^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 $$cleft(sright)$$ denote the number of $$i in left{1,2,ldots,nright}$$ 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(-1right)^j sum_{left|Iright| = j} left|A_Iright| = sum_{left|Iright| leq m} left(-1right)^{left|Iright|} left|A_Iright| = left(-1right)^m sum_{s in S} dbinom{cleft(sright) - 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(-1right)^m$$, because each of the binomial coefficients $$dbinom{cleft(sright) - 1}{m}$$ is nonnegative (indeed, each $$s in S$$ satisfies $$cleft(sright) geq 1$$ and thus $$cleft(sright) - 1 geq 0$$). Hence, the left hand side must have the same sign as $$left(-1right)^m$$ as well. This proves the claim. Let me know if you need more hints.

Answered by darij grinberg on January 1, 2022

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' = Xcup{n}$$ if $$nnotin X$$ or $$X'=Xsetminus {n}$$ if $$nin X$$. Note that $$(X')'=X$$ and thus $$(X,X')$$ partitions the family of all subsets of $$[n]$$. We denote $$S'={X';|;Xin S}$$.

Now, the given equation is equivalent to $$sum_{jtext{ even},jle m}binom{n}{j}-sum_{jtext{ odd},jle 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| (cannot be equal), it holds that $$|X'|le m$$. So $$I_2$$ contains $$I_1'$$ and $$|I_1|-|I_2|=-|I_2setminus I_1'|$$ corresponds to $$(-1)$$ times the number of $$Y$$ such that $$Yne X'$$ for all $$X$$. Since $$Y'ne X''=X$$ for all $$Xin I_1$$, it is equivalent to $$|Y'|=|Y|+1=m+1$$ and it follows that $$nnotin 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|, we must have $$|Y'|le m$$. This shows $$I_1$$ contains $$I_2'$$. And the difference $$I_1setminus I_2'$$ is the set of all $$X$$ for which $$Xne Y'$$ for all $$Y$$. This is equivalent to $$|X'|=|X|+1=m+1$$, i.e. $$|X|=m$$ and $$nnotin X$$. The number of such $$X$$ is equal to $$binom{n-1}{m}$$ and hence this proves $$|I_1|-|I_2| =|I_1setminus I_2'|= binom{n-1}{m}$$ for even $$m$$ case.

Answered by Myeonghyeon Song on January 1, 2022

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

Answered by Arthur on January 1, 2022

$$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)^nbinom{n}{n}x^n bigg](x^m+x^{m-1}+x^{m-2}+cdots +x+1).$$

Coeff. of $$x^{m}$$ in $$displaystyle (1-x)^ncdot 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}.$$

Answered by DXT on January 1, 2022

## Related Questions

### Why are all linear maps that sends one basis to another basis or to 0 still linear?

3  Asked on December 9, 2020

### Total variation regularization superior to classical quadratic choice

1  Asked on December 9, 2020 by pazu

### Why can we not expand $(a+b)^n$ directly when $n$ is a fractional or negative index?

1  Asked on December 8, 2020

### Let $A, B$ be skew-symmetric matrices such that $AB = -BA$. Show that $AB = 0$

1  Asked on December 8, 2020 by carlos-andres-henao-acevedo

### A question on locally integrable function on $mathbb{R}^n$

1  Asked on December 8, 2020 by kevin_h

### How to show that the integral is convergent without actually evaluating it?

4  Asked on December 8, 2020 by sandro-gakharia

### Saddle Point Approximation for Multiple Contour Integrals

0  Asked on December 8, 2020 by motherboard

### Finding minimum value of observation for a given power in hypothesis testing.

2  Asked on December 8, 2020 by hachiman-hikigaya

### What is sum of the Bernoulli numbers?

2  Asked on December 8, 2020 by zerosofthezeta

### Composition of two power series. We can compose two power series and get one power series. But why?

1  Asked on December 8, 2020 by tchappy-ha

### How much land space is required to meet the energy needs of the United States with solar?

0  Asked on December 7, 2020 by dev-dhruv

### Outer measure question (disjoint set st $lambda^*(A cup B) < lambda^*(A) + lambda^*(B)$)

1  Asked on December 7, 2020 by julian-ven

### Show that $mathbb{Z}[sqrt{3}]$ is dense in $mathbb{R}.$

1  Asked on December 7, 2020 by confusion

### Row Rank and Column vectors of Matrix

1  Asked on December 7, 2020 by james-black

### Applying the M-L estimate

1  Asked on December 7, 2020

### Stuck on Mathematical Induction Proof

2  Asked on December 7, 2020 by e__

### Depleted batteries

0  Asked on December 7, 2020 by francesco-totti

### Sphere’s surface area element using differential forms

2  Asked on December 7, 2020 by cryo

### Why the orthogonal complement of 0 is V?

2  Asked on December 6, 2020 by ivan-bravo