edited by
2,649 views
20 votes
20 votes

Let $A$ and $B$ be finite sets such that $A \subseteq B$. Then, what is the value of the expression:

$$ \sum \limits_{C:A \subseteq C \subseteq B} (-1)^{\mid C \setminus A \mid,}$$

Where $C \setminus A=\{x \in C : x \notin A \}$?

  1. Always $0$
  2. Always $1$
  3. $0$ if $A=B$ and $1$ otherwise
  4. $1$ if $A=B$ and $0$ otherwise
  5. Depends on the size of the universe
edited by

5 Answers

Best answer
9 votes
9 votes

Let set $B$ be of cardinality $n.$
Total subsets(A) possible are : $nC_0 + nC_1 + nC_2 + \ldots + nC_n.$ i.e $nC_r$ number of subsets exist with r cardinality.

Note that for each $r$, summation has $2^{n-r}$ terms to sum.
Case 1: $r= 0.$ which is $\emptyset$ .

Total terms $=2^{n}$.
Total terms when $|C\backslash A|$ even $= nC_0 + nC_2 + nC_4 + \ldots + nC(n-1)$ { if $n$ is odd, $nC_n$ otherwise }
Similarly, for odd $= 2^n - |C\backslash A|$
Even contributes to $1$ whereas odd contributes to $-1.$

Therefore, Summation $= 0$ as $2^n$ terms are present with half as $1$ & half as $-1.$
Case 2: $r = 1,$ total terms $=2^{n-1}$

Total terms when $|C\backslash A|$ even $= nC_r + nC_{r+2} + \ldots + nC_n$  { if $n$ is odd $n-1$ otherwise }
Total terms when $|C\backslash A|$ odd $= nC_{r+1} + nC_{r+3} + \ldots$
Again we are end up with total even terms with half contributing to $1$ & half $-1.$
same situation will arise for every $r ≠ n$ (as for such $r,$ $2^{r}$ is always even) i.e summation $= 0$ for all $r, r ≠ n.$
Case n: $r = n,$ total terms $=2^{n-n} = 1.$ This is the case when $B = A.$
$\therefore |C\backslash A| = 0$ as both are equal.
Summation $= 1.$
Therefore, answer is : $1$ if $A = B, 0$ otherwise.
Correct Answer: $D$

edited by
21 votes
21 votes

Very good QS.

13 votes
13 votes

I solved it diagrammatically and found it easier to solve

Case 1: When A=B : Then in this case you cannot find such a set C such that C is a subset of B and A is a proper subset of C where C has all elements A has, but C has atleast one element which A does not have.

So, in this case  cardinality of C\A would always be 0 no matter what C and A you take

So $\sum_{C : A \subseteq C \subseteq B}(-1)^{|C\setminus A|}$ would have only one case as A=C=B and so $(-1)^0=1$

So when A=B this will evaluate to 1.

Case 2: When A is a proper subset of B : In this case, we must have atleast one element say 'x' which will be contained in B but not in A.

Now here we can form out set C in two ways

(a) C=A : In this case $|C \setminus A|$ would be 0 and $(-1)^0=1.$

(b)C=B : In this case C would become a superset of A. and since we assumed B has one element extra than A, $|C \setminus A|=1$ and hence $(-1)^1=-1.$

Now $\sum_{C : A \subseteq C \subseteq B}(-1)^{|C\setminus A|}$$=1-1=0$

Image for Case 2:

4 votes
4 votes

$\underline{\textbf{Given}}$

$A$, $B$ are $\underline{\text{finite}}$ sets, such that $A \subseteq B$. We need to find $\sum_{C: A \subseteq C \subseteq B} (-1)^{|C-A|}$


$\underline{\textbf{Venn Diagram}}$

Let $|B| = n$ and $|A|=k$, then $|C-A|=m$


$\underline{\textbf{Observations}}$

For $|C-A|=m$ we only need to consider the count of such $m$ values and how many distinct types of $m$ values can be formed. But why we doing this? $m$ value will decide if $(-1)^m$ will be $1$ or $-1$, and count of specific $m$ value will decide the count of $1$ or $-1$. This can significantly reduce the above problem to simpler version, easing the further process of getting final solution. 

According to above figure $k \le |C| \le n$ same as $k \le \underbrace{\overbrace{|Y_1|}^{m}+\overbrace{|A|}^{k}}_{\substack{C = Y_1+A \\ Y_1 \cap A = \phi}} \le n$, this implies $\underbrace{0 \le m \le n-k}_{\text{distinct m values}}$. And for specific $m$ value, count is $^{n-k}C_m$.


$\underline{\textbf{Calculations}}$

$$\begin{align}
\sum_{C: A \subseteq C \subseteq B} (-1)^{|C-A|} &= \sum_{m=0}^{n-k} \ ^{n-k}C_m (-1)^m \\
&= (1+(-1))^{n-k} \tag{Binomial Expansion} \\
&= 0^{n-k}
\end{align}$$


$\underline{\textbf{Final Solution}}$

$0^{n-k} = \begin{cases}1 & n = k \implies A = B \\ 0 & n \neq k \implies \text{otherwise}\end{cases}$

$\textbf{Option (D) is correct}$


$\underline{\textbf{Reference for }0^0=1}$

Interesting read "What is 0^0"

Answer:

Related questions

40 votes
40 votes
2 answers
2
makhdoom ghaya asked Oct 26, 2015
3,082 views
How many pairs of sets $(A, B)$ are there that satisfy the condition $A, B \subseteq \left\{1, 2,...,5\right\}, A \cap B = \{\}?$$125$$127$$130$$243$$257$