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

Dark Mode

1,807 views

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 \}$?

- Always $0$
- Always $1$
- $0$ if $A=B$ and $1$ otherwise
- $1$ if $A=B$ and $0$ otherwise
- Depends on the size of the universe

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$

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

20 votes

0

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:

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

**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