Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I try to prove that the cardinality of the the symmetric difference of $n$ sets is
$$ \sum\limits_{i}|A_i|-2\sum\limits_{i<j}|A_i\cap A_j|+4\sum\limits_{i<j<k}|A_i\cap A_j\cap A_k|-\ldots $$ I try to use the Characteristic Function $\chi(x)$. I know that for a Symmetric difference $A\Delta B$ the Characteristic Function is $(\chi_A-\chi_B)^2$ and the cardinality of each set is $|X|=\sum_x\chi(x)$. but I do not know how to prove it for $n$ sets? So in that way I will have the characteristic function of each of one.

Many Thanks.

share|improve this question
2  
This is just induction and bookkeeping. You already know how to take the induction step because you know how the case of two sets behaves. Assume the formula is true for $n-1$ sets, then just use what you know to generate an expression true for the $n$ sets case, simplify it until you get the correct expression, then have a drink to relax after a long and tiresome proof. –  Asaf Karagila Aug 13 '12 at 10:53

1 Answer 1

up vote 6 down vote accepted

As Asaf said in the comments, this is bookkeeping and induction. I’m going to write out the induction step in full, but I’m going to do it in a very compact fashion that may not be easy to follow at first. I’m doing this for two reasons. First, you really ought to try to work out the induction step on your own, so I don’t want to make it too easy to read. (If you have trouble doing it in general, I suggest writing out the argument for $n=3$ and perhaps $n=4$ first; at that point you should be able to see fairly clearly what’s going on, and the main problem will likely be expressing it clearly in the general case.) Secondly, at some point you’ll want to get used to reading this sort of compact argument.

First let’s write out the sum in full:

$$\left|\bigoplus_{k=1}^nA_k\right|=\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\left|\bigcap_{i\in S}A_i\right|\;,\tag{1}$$

where I’ve used $\oplus$ for symmetric difference, and $[n]=\{1,\dots,n\}$. To avoid having too many subscripts, let $\chi_k$ be the characteristic function of $A_k$, and let $\varphi_n$ be the characteristic function of $\bigoplus_{k=1}^nA_k$. Then $(1)$ will certainly be true if

$$\varphi_n=\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i\;,\tag{2}$$

since $\prod_{i\in S}\chi_i$ is the characteristic function of $\bigcap_{i\in S}A_i$.

You can prove $(2)$ by induction on $n$. You need to use the fact that for any characteristic function $\chi$, $\chi^2=\chi$. You already know that $\chi_{A\oplus B}=(\chi_A-\chi_B)^2$. Now for the induction step you have

$$\begin{align*} \varphi_{n+1}&=\left(\varphi_n-\chi_{n+1}\right)^2\\ &=\varphi_n^2+\chi_{n+1}^2-2\varphi_n\chi_{n+1}\\ &=\varphi_n+\chi_{n+1}-2\varphi_n\chi_{n+1}\\ &=\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i+\chi_{n+1}-2\chi_{n+1}\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i\tag{3} \end{align*}$$

for starters. The first term in $(3)$ can be split as

$$\sum_{i\in[n]}\chi_i+\sum_{k=2}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i\tag{4}$$

and the first term of $(4)$ can be combined with the $\chi_{n+1}$ term in $(3)$ to yield

$$\begin{align*} \varphi_{n+1}&=\sum_{i\in[n+1]}\chi_i+\sum_{k=2}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i-2\chi_{n+1}\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i\\ &=\sum_{i\in[n+1]}\chi_i+\sum_{k=2}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i-2\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i\chi_{n+1}\tag{5}\;. \end{align*}$$

Now let $S$ be a subset of $[n+1]$ such that $|S|=k$. If $k=1$, then $\prod_{i\in S}$ is one of the $\chi_i$, and it appears in the first term of $(5)$ with coefficient $1=(-1)^02^0=(-1)^{k-1}2^{k-1}$.

Suppose now that $1<k\le n$. If $n+1\notin S$, $\prod_{i\in S}\chi_i$ is counted in the second term of $(5)$, where it appears with coefficient $(-1)^{k-1}2^{k-1}$. If $n+1\in S$, then $\prod_{i\in S}\chi_i$ appears in the last term of $(5)$ as $\prod_{i\in S'}\chi_i\chi_{n+1}$, where $S'=S\setminus\{n+1\}$, and $|S'|=k-1$. In this case the coefficient of $\prod_{i\in S}\chi_i$ is $-2(-1)^{k-2}2^{k-2}=(-1)^{k-1}2^{k-1}$.

Finally, suppose that $k=n+1$. Then $S=[n+1]$, and $\prod_{i\in S}\chi_i=\prod_{i\in[n]}\chi_i\chi_{n+1}$ appears in the last term of $(5)$ with coefficient $-2(-1)^{n-1}2^{n-1}=(-1)^n2^n=(-1)^{k-1}2^{k-1}$.

It follows that $(5)$ (and hence $\varphi_{n+1}$) is equal to

$$\sum_{k=1}^{n+1}(-1)^{k-1}2^{k-1}\sum_{S\subset[n+1]\atop|S|=k}\prod_{i\in S}\chi_i\;,$$

which completes the induction step.


By the way, a simpler approach is to show that $a\in\bigoplus_{k=1}^nA_k$ iff $|\{k\in[n]:a\in A_k\}|$ is odd, which is an easy induction, and then to show that that the righthand side of $(1)$ counts the elements of $\bigcup_{k=1}^nA_k$ that are in an odd number of the $A_k$. This is a fairly easy consequence of the binomial theorem. If an element $a$ is in exactly $m$ of the $n$ sets, for each $k$ from $1$ through $m$ it’s in $\binom{m}k$ $k$-fold intersections, so it contributes

$$\begin{align*} \sum_{k=1}^m\binom{m}k(-1)^{k-1}2^{k-1}&=-\frac12\sum_{k=1}^m\binom{m}k(-2)^k\\ &=-\frac12\left(\sum_{k=0}^m\binom{m}k(-2)^k-1\right)\\ &=\frac12\Big(1-(1-2)^m\Big)\\ &=\frac{1-(-1)^m}2\\ &=\begin{cases} 1,&\text{if }m\text{ is odd}\\ 0,&\text{if }m\text{ is even} \end{cases} \end{align*}$$

to the righthand side of $(1)$.

share|improve this answer
    
+1 This is heroic! –  Norbert Aug 13 '12 at 14:05
    
Many Thanks Brian and Asaf –  Hernan Aug 13 '12 at 14:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.