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

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

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.

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.

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

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