Equation for cardinality of the union of $n$ sets Let $A_1,\dots,A_n$ be finite sets.
I want to show the following equation.
$\lvert A_1 \cup \dots \cup A_n \rvert = \displaystyle\sum_{k=1}^n{(-1)^{k+1}\left( \displaystyle\sum_{1 \leq i_1 \lt \dots \lt i_k \leq n} {\lvert A_{i_1} \cap \dots \cap A_{i_k} \rvert} \right)}$
I want to proof it by induction and I think might be useful that
$\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$
for finite sets $A$, $B$.
I don't get any further when I try to write down the induction step.
 A: You’re quite right that the two-set case is used in the induction step, but it’s still a little tricky to work through.
Suppose that you know it for $n$. Let $B=A_1\cup\ldots\cup A_n$. Then
$$\begin{align*}
|A_1\cup\ldots\cup A_{n+1}|&=|B\cup A_{n+1}|\\
&=|B|+|A_{n+1}|-|B\cap A_{n+1}|\\
&=\sum_{k=1}^n(-1)^{k+1}\left(\sum_{1\le i_1<\ldots<i_k\le n}|A_{i_1}\cap\ldots\cap A_{i_k}|\right)+|A_{n+1}|-|B\cap A_{n+1}|\;.\tag{1}
\end{align*}$$
Now
$$\begin{align*}
|A_{n+1}|-|B\cap A_{n+1}|&=|A_{n+1}|-\left|\left(\bigcup_{k=1}^nA_k\right)\cap A_{n+1}\right|\\
&=|A_{n+1}|-\left|\bigcup_{k=1}^n(A_k\cap A_{n+1})\right|\\
&=|A_{n+1}|-\sum_{k=1}^n(-1)^{k+1}\left(\sum_{1\le i_1<\ldots<i_k\le n}|(A_{i_1}\cap A_{n+1})\cap\ldots\cap(A_{i_k}\cap A_{n+1})|\right)\\
&=|A_{n+1}|+\sum_{k=1}^n(-1)^{k+2}\left(\sum_{1\le i_1<\ldots<i_k\le n}|A_{i_1}\cap\ldots\cap A_{i_k}\cap A_{n+1}|\right)\\
&=\sum_{k=1}^{n+1}(-1)^{k+1}\left(\sum_{1\le i_1<\ldots<i_{k-1}\le n<i_k=n+1}|A_{i_1}\cap\ldots\cap A_{i_k}|\right)\tag{2}
\end{align*}$$
by the induction hypothesis applied to the $n$ sets $A_1\cap A_{n+1},\ldots,A_n\cap A_{n+1}$. 
To see what’s really going on here, it’s helpful to realize that the sum $(2)$ covers all of the intersections of $A_i$s that include the new $A_{n+1}$, while the first term of $(1)$ covers the ones that don’t include $A_{n+1}$. Combining results, we now have
$$\begin{align*}
\left|\,\bigcup_{k=1}^{n+1}A_k\,\right|&=\sum_{k=1}^n(-1)^{k+1}\left(\sum_{1\le i_1<\ldots<i_k\le n}|A_{i_1}\cap\ldots\cap A_{i_k}|\right)\\
&\qquad+\sum_{k=1}^{n+1}(-1)^{k+1}\left(\sum_{1\le i_1<\ldots<i_{k-1}\le n<i_k=n+1}|A_{i_1}\cap\ldots\cap A_{i_k}|\right)\\
&=\sum_{k=1}^{n+1}(-1)^{k+1}\left(\sum_{1\le i_1<\ldots<i_k\le n+1}|A_{i_1}\cap\ldots\cap A_{i_k}|\right)\;,
\end{align*}$$
as desired.
