GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
77 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
asked in Set Theory & Algebra by Veteran (78.2k points)   | 77 views

2 Answers

+2 votes

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. 

answered by Loyal (3.7k points)  
perfect ! rohit (y)
Thank you. :)
+1 vote

Very good QS.

answered by Veteran (50.5k points)  


Top Users Jul 2017
  1. Bikram

    4062 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1850 Points

  4. joshi_nitish

    1658 Points

  5. Arjun

    1294 Points

  6. Hemant Parihar

    1184 Points

  7. Arnab Bhadra

    1112 Points

  8. Shubhanshu

    1054 Points

  9. Ahwan

    900 Points

  10. rahul sharma 5

    706 Points


24,022 questions
30,966 answers
70,346 comments
29,342 users