I am trying to proof the inclusion-exclusion principle and I can't find anything on the internet that matches the formula that I have to proof. I need to proof the following.
$$\#(\bigcup_{j=1}^{n} X_{j}) = \sum_{D \subset E_{n}} (-1)^{\#D-1}\#X_{D}$$ where $$X_{D}=\bigcap_{j\in D} X_{j}$$ So for example $X_{\{i,j,k\}} = X_{i} \cap X_{j} \cap X_{k}$
I am trying to proof this by induction.
Basic step: $n=1$ then $$\#(X_{1}) =\#(X_{1})$$ which is trivial.
Now assume that the formula is correct for $n=k$, namely $$\#(\bigcup_{j=1}^{k} X_{j}) = \sum_{D \subset E_{k}} (-1)^{\#D-1}\#X_{D}.$$ We will proof that it is also correct for $n=k+1$. So $$\#(\bigcup_{j=1}^{k+1} X_{j}) = \sum_{D \subset E_{k+1}} (-1)^{\#D-1}\#X_{D}.$$ I have no idea what my next step should be.