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

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

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

• Thanks, I have updated a post – Tester1998 Aug 15 at 11:32
• @Tester1998 I edited my answer. – Robert Z Aug 15 at 12:05
• I didn't know that linked equality. In exercises like that it is worth to know about some of them. very clear solution. Big thanks for you – Tester1998 Aug 15 at 12:32

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