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|<m$ (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|<m$, 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

3 Asked on December 9, 2020

1 Asked on December 9, 2020 by buyanov-igor

1 Asked on December 9, 2020 by pazu

image processing inverse problems reference request regularization total variation

1 Asked on December 8, 2020

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

1 Asked on December 8, 2020 by kevin_h

4 Asked on December 8, 2020 by sandro-gakharia

0 Asked on December 8, 2020 by motherboard

approximate integration combinatorial proofs combinatorics contour integration

2 Asked on December 8, 2020 by hachiman-hikigaya

hypothesis testing normal distribution statistical inference

1 Asked on December 8, 2020 by tchappy-ha

0 Asked on December 7, 2020 by dev-dhruv

1 Asked on December 7, 2020 by julian-ven

1 Asked on December 7, 2020 by confusion

1 Asked on December 7, 2020 by james-black

0 Asked on December 7, 2020 by francesco-totti

2 Asked on December 7, 2020 by cryo

2 Asked on December 6, 2020 by ivan-bravo

bilinear form elementary set theory linear algebra orthogonality vector spaces

Get help from others!

Recent Answers

- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Joshua Engel on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir