Show that the number of elements of $X$ belonging to a least $r$ equals to $\sum_{k=r}^n(-1)^{k-r}{k-1\choose r-1}S_k$

Question

Show that the number of elements of $X$ belonging to a least $r$ of the sets $A_1,\ldots,A_n\subset X$ is $$\sum_{k=r}^n(-1)^{k-r}{k-1\choose r-1}S_k.$$

$S_k$ is defined here as: $$ \sum_{1 \le i_1 < \cdots< i_k \le n} |A_{i_1} \cap ... \cap A_{i_k}|$$

My try.

From link we know that number of elements of $X$ belonging to $r$ sets is $$ L(k) = \sum_{i=k}^n (-1)^{i-k} \binom{i}{k}S_i $$

So number of elements of $X$ belonging to a least $r$ of the sets is equal to $$L(k) + L(k+1) + L(k+2) + \cdots + L(n) $$

So let do this: \begin{align} & \binom{r}{r}S_r - \binom{r+1}{r}S_r + \color{red}{\binom{r+2}{r}}S_r -... \pm \binom{n}{r}S_n + \\ & 0 + \binom{r+1}{r+1}S_r - \color{red}{\binom{r+2}{r+1}}S_r +... \mp \binom{n}{r+1}S_n +\\ & 0 + 0 + \color{red}{\binom{r+2}{r+2}}S_r -... \mp \binom{n}{r+2}S_n + \\&\vdots\\\\ & 0+0+\color{red}{0}+0+0+0+0+0+\cdots \pm S_n \end{align} I think that summing by cols can give me proof. But I have some troubles with proof that: $$\sum _{k=0}^t (-1)^k \binom{r+t}{k+r} = \binom{r+t-1}{r-1}.$$

Answer 1

By Combinatorial proof that $\sum_{j=0}^k (-1)^j {\binom n j}=(-1)^k \binom{n-1}{k}$, after setting $n=r+t$ and $k=t$, we find $$\sum _{k=0}^t (-1)^k \binom{r+t}{k+r}=\sum _{k=0}^t (-1)^k \binom{r+t}{t-k}= (-1)^t\sum _{j=0}^t (-1)^j \binom{r+t}{j}=\binom{r+t-1}{t}=\binom{r+t-1}{r-1} .$$

Answer 2

Let $B_{r}:=\left\{ x\in X\mid\sum_{i=1}^{n}\mathbf{1}_{A_{i}}\left(x\right)\geq r\right\} $ so is the set of elements of $X$ belonging to at least $r$ of the sets $A_1,\dots,A_n\subseteq X$.

In this answer it will be shown that: $$\mathbf{1}_{B_{r}}=\sum_{k=r}^{n}\left(-1\right)^{k-r}\binom{k-1}{r-1}\sum_{i_{1}<\cdots<i_{k}}\mathbf{1}_{A_{i_{1}}\cap\cdots\cap A_{i_{k}}}\tag1$$ What you asked in your question is a direct consequence of this equality.

---

Lemma: if $S\left(u,v\right):=\sum_{k=u}^{v}\left(-1\right)^{k-u}\binom{k-1}{u-1}\binom{v}{k}$ for integers $u,v$ with $1\leq u\leq v$ then $S\left(u,v\right)=1$.

Proof of lemma: In special case $u=1$ it must be proved that: $$\sum_{k=1}^{v}\left(-1\right)^{k-1}\binom{v}{k}=1$$ for integer $v\geq1$ which goes like this:

$$\sum_{k=1}^{v}\left(-1\right)^{k-1}\binom{v}{k}=1-\sum_{k=0}^{v}\left(-1\right)^{k}1^{v-k}\binom{v}{k}=1-\left(\left(-1\right)+1\right)^{k}=1$$

In the sequel we will prove that for $u\geq2$ we have: $$S\left(u,v\right)=S\left(u-1,v-1\right)$$ This is enough to prove the lemma because by repetition we find: $$S\left(u,v\right)=S\left(u-1,v-1\right)=\cdots=S\left(1,v-u+1\right)=1$$

Applying the convention that a binomial coefficient $\binom{n}{k}$ takes value $0$ if $n$ is a nonnegative integer and $k$ is an integer that satisfies $k\notin\left\{ 0,\dots,n\right\} $ we find:

$$\begin{aligned}S\left(u,v\right) & =\sum_{k\in\mathbb{Z}}\left(-1\right)^{k-u}\binom{k-1}{u-1}\binom{v}{k}\\ & =\sum_{k\in\mathbb{Z}}\left(-1\right)^{k-u}\binom{k-1}{u-1}\left[\binom{v-1}{k-1}+\binom{v-1}{k}\right]\\ & =\sum_{k\in\mathbb{Z}}\left(-1\right)^{k-u}\binom{k-1}{u-1}\binom{v-1}{k-1}+\sum_{k\in\mathbb{Z}}\left(-1\right)^{k-u}\binom{k-1}{u-1}\binom{v-1}{k}\\ & =\sum_{k\in\mathbb{Z}}\left(-1\right)^{k+1-u}\binom{k}{u-1}\binom{v-1}{k}+\sum_{k\in\mathbb{Z}}\left(-1\right)^{k-u}\binom{k-1}{u-1}\binom{v-1}{k}\\ & =\sum_{k\in\mathbb{Z}}\left(-1\right)^{k+1-u}\binom{k}{u-1}\binom{v-1}{k}-\sum_{k\in\mathbb{Z}}\left(-1\right)^{k+1-u}\binom{k-1}{u-1}\binom{v-1}{k}\\ & =\sum_{k\in\mathbb{Z}}\left(-1\right)^{k+1-u}\left[\binom{k}{u-1}-\binom{k-1}{u-1}\right]\binom{v-1}{k}\\ & =\sum_{k\in\mathbb{Z}}\left(-1\right)^{k-\left(u-1\right)}\binom{k-1}{u-2}\binom{v-1}{k}\\ & =S\left(u-1,v-1\right) \end{aligned} $$

End of proof lemma.

Theorem: Equality $(1)$ is valid.

We will use the lemma to prove this theorem.

This by showing that by substituion for every $x\in X$ we find the on LHS and RHS of $(1)$ the same value.

For a fixed $x\in X$ let $J_{x}=\left\{ i\in\left\{ 1,\dots,n\right\} \mid x\in A_{i}\right\} $.

If $\left|J_{x}\right|<r$ then evidently substituting $x$ gives $0$ on both sides of $\left(1\right)$.

Now if we let $\left|J_{x}\right|=m\geq r$ then we find outcome $1$ on LHS of $\left(1\right)$ and it remains to prove that we also find $1$ as outcome on RHS.

On RHS we find that $\mathbf{1}_{A_{i_{1}}\cap\cdots\cap A_{i_{k}}}\left(x\right)=1$ if $\left\{ i_{1},\dots,i_{k}\right\} \subseteq J_{x}$ and $\mathbf{1}_{A_{i_{1}}\cap\cdots\cap A_{i_{k}}}\left(x\right)=0$ otherwise.

That implies that: $$\sum_{i_{1}<\cdots< i_{k}}\mathbf{1}_{A_{i_{1}}\cap\cdots\cap A_{i_{k}}}\left(x\right)=\binom{m}{k}$$

so that indeed:$$\sum_{k=r}^{n}\left(-1\right)^{k-r}\binom{k-1}{r-1}\sum_{i_{1}<\cdots< i_{k}}\mathbf{1}_{A_{i_{1}}\cap\cdots\cap A_{i_{k}}}\left(x\right)=\sum_{k=r}^{n}\left(-1\right)^{k-r}\binom{k-1}{r-1}\binom{m}{k}=S\left(r,m\right)=1$$

End of theorem.

Consequence of theorem:$$\left|B_{r}\right|=\sum_{k=r}^{n}\left(-1\right)^{k-r}\binom{k-1}{r-1}S_{k}\tag2$$This consequence appears if on on both sides of $(1)$ we take the integral with respect to the counting measure.