compute $\sum_{I\subseteq K }(-1)^{\mid K\setminus I\mid}$

40 Views Asked by At

Let I and K be finite set. compute $\sum_{I\subseteq K }(-1)^{\mid K\setminus I\mid}$

Here is I come up with,

$\sum_{I\subseteq K }(-1)^{\mid K\setminus I\mid} =\sum_{i=0}^{k}{k \choose i}(-1)^{i} = 0$

and why I have this is because, we know I is subset of K, and I has the size 0, 1, 2, 3, ... to k, where k is the size of set K. For each size of I, we have ${k \choose i}$ ways to choose i elements

There is ${k \choose i}$ ways for each i, and we sum over i from $0$ to k such that we can calculate all $(-1)^{\mid K\setminus I\mid}$

Then by binomial theorem, we have $\sum_{i=0}^{k}{k \choose i}(-1)^{i} = 0$

Do you think this is correct?

1

There are 1 best solutions below

2
On BEST ANSWER

Your argument is correct if $k>0$. If $k=0$, you get

$$\sum_{i=0}^0\binom0i(-1)^i=\binom00(-1)^0=1\;.$$

Another way to look at it is to notice that as $I$ ranges over all subsets of $K$, so does $K\setminus I$, so you’re really just computing $\sum_{I\subseteq K}(-1)^{|I|}$. Call a subset of $K$ even if its cardinality is even, and odd if its cardinality is odd. Then each even subset of $K$ contributes a $+1$ term, and each odd subset of $K$ contributes a $-1$ term, so the sum is just the number of even subsets of $K$ minus the number of odd subsets of $K$. Every non-empty set has the same number of even and odd subsets, so for $K\ne\varnothing$ the sum is $0$. The empty set has one even subset — itself — and no odd subset, so for $K=\varnothing$ the sum is $1$.

The fact that exactly half of the subsets of a non-empty set are even can be proved by your argument, but it can also be proved by other arguments, so using it to prove your result need not be circular.