Inclusion-exclusion principle question 1st part of my question: 
I have that $$P\left(\bigcup_{i=1}^{{2^n-n}}E_i\right)$$
, how would I write it out using the inclusion-exclusion principle? I know it starts off: $$\sum_{i=1}^{2^n-n} P(E_i)+...$$ But after that Im not sure what goes next.
2nd part --- I also read somewhere that (by subadditivity), $P\left(\bigcup_{i=1}^{{2^n-n}}E_i\right) \le \sum_{i=1}^{2^n-n} P(E_i)$, but why is that the case? I dont understand how it by subadditivity the above inequality comes about.
Thanks.
 A: $$\eqalign{
P\Bigl(\bigcup_{i=1}^n E_i\Bigr) = 
\sum_{i\le n} P(E_i) - &\sum_{i_1<i_2}\underbrace{ P(E_{i_1}\cap E_{i_2})}_{
{\text {two at a time}}}
   +\sum_{i_1<i_2<i_3} \underbrace{ P(E_{i_1}\cap E_{i_2}\cap E_{i_3})}_{\text {three at a time}} - \cr
 &\cdots+ (-1)^{n}\sum_{i_1<i_2<\cdots<i_{n-1} } 
 \underbrace{ P(E_{i_1}\cap\cdots\cap E_{i_{n-1}} )}_{(n-1)\text {  at a time}}  \cr

&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + (-1)^{n+1}P(E_1\cap E_2\cap\cdots\cap E_n)}
$$
The subscripts in the above sums are just a handy way to write, for example in the term $\sum\limits_{i_1<i_2}  P(E_{i_1}\cap E_{i_2})  $, 
"take the sum of the probabilities of   intersections of two distinct events (the intersections taken without regard to order; that is, in the sum, you have only only 
one of, e.g., $P(E_1\cap E_2)$ or $P(E_2\cap E_1) \thinspace $)".  
Of course  my "$n$" is your "$2^n-n$".
For your concern at the end of your post,
note the formula above has negative terms.
In general, if the events $\{E_i\}$ are mutually exclusive, then $P(\cup E_i )=\sum P(E_i)$; but if the events overlap then  $P(\cup E_i )\le\sum P(E_i)$. This is because the right hand side of the preceeding formula counts some probabilities more than once (namely those in the intersection of overlapping $E_i$).
A: $$\sum_{i=1}^{2^n-n} P(E_i) - \sum_{i=2}^{2^n-n} \sum_{j=1}^{i-1} P(E_i \cap E_j) + \sum_{i=3}^{2^n-n} \sum_{j=2}^{i-1} \sum_{k=1}^{j-1} P(E_i \cap E_j\cap E_k) -\cdots$$
The key point about the limits of the sums is you want each possible combination once and the $i,j,k,\ldots$ distinct
For the second part you have 
$$ P\left(\bigcup_{i=1}^{{2^n-n}}E_i\right) = P(E_1)+P(E_2 \cap E_1^C)+ P(E_3 \cap E_2^C \cap E_1^C) + \cdots$$ 
$$\le P(E_1)+P(E_2)+ P( E_3) + \cdots =  \sum_{i=1}^{2^n-n} P(E_i) $$
