in Set Theory & Algebra edited by
1,807 views
19 votes
19 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
in Set Theory & Algebra edited by
1.8k views

4 Answers

9 votes
9 votes
Best answer

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

4 Comments

@Manoja-In that case, you'll have 3 more subcases.

Say, B has extra $x_1,x_2$ elements which are not in A

The very first case is when C=A

When take another case when C=A+$x_1$

Then another case C=A+$x_2$

Then last case C=A+$x_1+x_2=B$

Sum up all you'll get 0
5
5

I got it. Thank you :) @Ayush Upadhyaya

suggestion: You can post this as 'Answer' instead of comment. Your solution is easy to understand.

1
1
reshown by

Could anyone please explain below part in the given answer?

Total terms when |C∖A||C∖A| even =nC0+nC2+nC4+…+nC(n−1)=nC0+nC2+nC4+…+nC(n−1) { if nn is odd, nCnnCn otherwise }
Similarly for odd =2n−|C∖A|

0
0
20 votes
20 votes

Very good QS.

by

3 Comments

Nice explanation.Thanks,  Debashish Deka.

1
1

Just small edit: Sum= (1-1)^k  [since according to binomial theorem

(x+y)^{n}={n \choose 0}x^{n}y^{0}+{n \choose 1}x^{n-1}y^{1}+{n \choose 2}x^{n-2}y^{2}+\cdots +{n \choose n-1}x^{1}y^{n-1}+{n \choose n}x^{0}y^{n},

here x=1, y=-1, n=k]

So, Sum =0^k . If k=0 then Sum=1 , otherwise Sum =0

0
0
best explanation for such complex question
0
0
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 Comments

Yes I understood that.. But suppose A={1,2,3}, B={1,2,3,4,5,6,7,8} and C can be {1,2,3},{1,2,3,4},{1,2,3,4,5}...{1,2,3,4,5,6,7,8}. My question was why did you take C only as {1,2,3} and {1,2,3,4,5,6,7,8}? Where are the other cases of C..?
0
0

@MiNiPanda-To make things short and solve this in competitive exam I have given this solution.
You take case where Set B has 2 element extra than Set A and then consider all possible cases of set C.

You'll find out still result will be 0.

I did it for 1,2,3 elements and then after that I had posted this.

0
0

@Ayush Upadhyaya

didn't it depends upon size of A and B ?

let B={1,2,3,4} and A={1} ==> |B| = even and  |A|=odd

C can be {1},{1,2},{1,2,3},{1,2,3,4} ==> |C-A| = 0,1,2,3 respectively 

then the summation is = (-1)$^0$ + (-1)$^1$ + (-1)$^2$ + (-1)$^3$ = 1-1+1-1 = 0

 

let B={1,2,3,4} and A={1,2} ==> |B| = even and |A|=even

C can be {1,2},{1,2,3},{1,2,3,4} ==> |C-A| = 0,1,2 respectively 

then the summation is = (-1)$^0$ + (-1)$^1$ + (-1)$^2$ = 1-1+1 = 1

 

let B={1,2,3,4,5} and A={1} ==> |B| = odd and |A|=odd

C can be {1},{1,2},{1,2,3},{1,2,3,4},{1,2,3,4,5} ==> |C-A| = 0,1,2,3,4 respectively 

then the summation is = (-1)$^0$ + (-1)$^1$ + (-1)$^2$ + (-1)$^3$ + (-1)$^4$ = 1-1+1-1+1 = 1

 

let B={1,2,3,4,5} and A={1,2} ==>|B| = odd and |A|=even

C can be {1,2},{1,2,3},{1,2,3,4},{1,2,3,4,5} ==> |C-A| = 0,1,2,3 respectively 

then the summation is = (-1)$^0$ + (-1)$^1$ + (-1)$^2$ + (-1)$^3$ = 1-1+1-1 = 0

2
2
0 votes
0 votes

Correct option is (D) 1 if A=B and 0 otherwise

1 comment

Why in my example odd and even terms are not equal  according to formula ?

0
0
Answer:

Related questions