Why are there $2^n-1$ terms in the inclusion-exclusion formula of $n$ sets?

Question

Why are there $2^n-1$ terms in the inclusion-exclusion formula of $n$ sets?

An example of what I mean by inclusion-exclusion formula is this:

There are three sets (i.e. $n$ $=$ $3$): $A, B,$ and $C$.

$A \cup B \cup C = |A| +|B|+|C|-|A\cap B| - |A\cap C| - |B \cap C| +|A \cap B \cap C| $

There are $2^3-1 =7$ terms in the right hand side of the equation.

This seems to be true in general, but I'm not sure why. It's probably something obvious I'm missing, can anyone give me a hint?

Answer 1

The amount of terms can be calculated as $\Sigma_{i = 1}^n \binom{n}{i}$. Using the binomial theorem we get: $$\Sigma_{i = 1}^n \binom{n}{i} = \Sigma_{i=0}^n \binom{n}{i}1^i1^{n - i} - 1 = (1 + 1)^n - 1 = 2^n - 1$$

Answer 2

Of the first kind (one set) there are $\binom{3}{1}$ terms (we use just 1 set from the 3 we have).

Of the second kind, $\binom{3}{2}$ terms (that many pairs from 3 elements)

Of the last kind $\binom{3}{3}=1$ many.

Note that Newton's binomial $$(1+x)^n = \sum_{i=0}^n \binom{n}{i}x^i$$

implies (by taking $x=1$ and moving the $\binom{n}{0}=1$ to the left) that $$2^n - 1 = \sum_{i=1}^n \binom{n}{i}$$

and on the right we have the number of terms for $n$ sets.

Answer 3

This is because you have to take these sets $1$ by $1$, then $2$ by $2$, &c. and ultimately $n$ by $n$, which makes all nonempty subsets of the set $\{A_1,A_2,\dots, A_n\}$, and because there are $2^n$ subsets of a set with $n$ elements (including the empty subset).