How to simplify an expression where the summation is over all subsets of a given set?

Question

I want to simplify this expression:

$\sum\limits_{\emptyset \ne I \subseteq \mathbb{N}_k}(-1)^{|I|-1}|A_I|+|A_{k+1}|-\sum\limits_{\emptyset \ne I \subseteq \mathbb{N}_k}(-1)^{|I|-1}|A_I \cap A_{k+1}|$

To this expression:

$\sum\limits_{\emptyset \ne I \subseteq \mathbb{N}_{k+1}} (-1)^{|I|-1}|A_I|$

where:

$A_1,A_2, \dots, A_n $ are finite sets

For $I=\{i_1,i_2, \dots , i_r\}\subseteq \mathbb{N}_n$, write $A_I=\bigcap_{i\in I}A_i=A_{i_1}\cap A_{i_2}\cap \dots \cap A_{i_r}$

If the summation were over some integers, then I would usually expand the summation operator and see how that new expression can be further simplified.

In this case, the summation is over all possible subsets of $\mathbb{N}_k$ so I don't know how to expand this in general (what to write in order to keep track all the possible individual terms in each summation). Please show me the steps to simplify this expression and the reasoning behind each steps.

Answer 1

The contributions to the first expansion are:

• the nonempty sets $I\subseteq\mathbb N_k$
• the set $\{k+1\}$
• the sets $I\cup\{k+1\}$ with $I$ nonempty, $I\subseteq\mathbb N_k$

These are exactly the nonempty subsets $J$ of $\mathbb N_{k+1}$, each counted with the sign $(-1)^{|J|-1}$, hence the result.