2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks, I have updated a post $\endgroup$ – Tester1998 Aug 15 at 11:32
  • $\begingroup$ @Tester1998 I edited my answer. $\endgroup$ – Robert Z Aug 15 at 12:05
  • $\begingroup$ 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 $\endgroup$ – Tester1998 Aug 15 at 12:32
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.