67 views

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

$$\Sigma_{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 soze of the universe

Let set B be of cardinality n.

Total subsets(A) possible are : nC0 + nC1 + nC2 + ... + nCn. i.e nCr 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 $\Phi$ .

Total terms = $2^{n}$.

Total terms when |C\A| even = nC0 + nC2 + nC4 + ... + nC(n-1) { if n is odd, nCn otherwise }

Similarly for odd = 2ⁿ - |C\A|

Even contributes to 1 whereas odd contributes to -1.

Therefore Summation = 0 as 2ⁿ terms are present with half as 1 & half as -1.

Case 2: r = 1 , total terms = $2^{n-1}$

Total terms when |C\A| even = nCr + nC(r+2) + ... + nCn  { if n is odd n-1 otherwise }

Total terms when |C\A| odd = nC(r+1) + nC(r+3) + ...

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\A| = 0 as both are equal.

Summation = 1.

therefore answer is : 1 if A = B, 0 otherwise.

Lemme know if I'm wrong.

perfect ! rohit (y)
Thank you. :)
+1 vote

Very good QS.

1
+1 vote
2
+1 vote