GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
62 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 (73.4k points)   | 62 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 (3k points)  
perfect ! rohit (y)
Thank you. :)
+1 vote

Very good QS.

answered by Veteran (37.6k points)  
Top Users Jan 2017
  1. Debashish Deka

    9716 Points

  2. sudsho

    5558 Points

  3. Bikram

    5290 Points

  4. Habibkhan

    4990 Points

  5. Vijay Thakur

    4498 Points

  6. Arjun

    4418 Points

  7. saurabh rai

    4236 Points

  8. Sushant Gokhale

    4226 Points

  9. Kapil

    3848 Points

  10. santhoshdevulapally

    3808 Points

Monthly Topper: Rs. 500 gift card

19,449 questions
24,228 answers
53,953 comments
20,373 users