91Ó°ÊÓ

For a finite set$A$, let'slocalid="1649342090814" $N\left(A\right)$denote the number of elements$A$.

Let's count the number of elements$A∪B$directly. There are $\mathrm{N}\left(\mathrm{A}\right)+\mathrm{N}\left(\mathrm{B}\right)$elements if we count them separately. But notice that we counted the elements localid="1649342106325" $Aâˆ\copyright B$twice. Hence

$N(A∪B=N(A)+N(B)-N(Aâˆ\copyright B).$

We will apply mathematical induction to the number of sets. For$n=2$, see Part$\left(a\right)$. Now assume for$n=k$we have.$N\left(A_1∪A_2∪…∪A_k\right)=\underset{i=1}{\overset{k}{∑}}N\left(A_i\right)-\underset{i_1<i_2}{∑}N\left(A_{i_1}âˆ\copyright A_{i_2}\right)+…+(-1{)}^{r+1}\underset{i_1<…<i_r}{∑}N\left(A_{i_1}âˆ\copyright …âˆ\copyright A_{i_r}\right)+…+(-1{)}^{k+1}N\left(A_1âˆ\copyright …âˆ\copyright A_k\right)$

For$n=k+1$. Set $A=A_1∪…∪A_k$and apply Part$\left(a\right)$. Then we get

$N\left(A_1∪A_2∪…∪A_k∪A_{k+1}\right)=N\left(A\right)+N\left(A_{k+1}\right)-N\left(Aâˆ\copyright A_{k+1}\right)$

Using the induction hypothesis we get

$N\left(A_1∪A_2∪…∪A_{k+1}\right)=N\left(A\right)+N\left(A_{k+1}\right)-N\left(Aâˆ\copyright A_{k+1}\right)$

$N\left(A_1∪A_2∪…∪A_{k+1}\right)=N\left(A_{k+1}\right)+\underset{i=1}{\overset{k}{∑}}N\left(A_i\right)-\underset{i_1<i_2}{∑}N\left(A_{i_1}âˆ\copyright A_{i_2}\right)+…+(-1{)}^{r+1}\underset{i_1<…<i_r}{∑}N\left(A_{i_1}âˆ\copyright …âˆ\copyright A_{i_r}\right)+…+(-1{)}^{k+1}N\left(A_1…A_k\right)-N\left(Aâˆ\copyright A_{k+1}\right)$

Now observe that

$$\begin{gathered} N\left(Aâˆ\copyright A_{k+1}\right)=N\left(\left(A_1∪…∪A_k\right)âˆ\copyright A_{k+1}\right) \\ =N\left(\left(A_1âˆ\copyright A_{k+1}\right)∪…∪\left(A_kâˆ\copyright A_{k+1}\right)\right) \\ =\underset{i=1}{\overset{k}{∑}}N\left(A_iâˆ\copyright A_{k+1}\right)-\underset{i_1<i_2}{∑}N\left(A_{i_1}âˆ\copyright A_{i_2}âˆ\copyright A_{k+1}\right)+…+(-1{)}^{r+1}\underset{i_1<…<i_r}{∑}N\left(A_{i_1}âˆ\copyright …âˆ\copyright A_{i_r}âˆ\copyright A_{k+1}\right) \\ +…+(-1{)}^{k+1}N\left(A_1âˆ\copyright …âˆ\copyright A_kâˆ\copyright A_{k+1}\right) \end{gathered}$$

Combining this with the identity above we get

$N\left(A_1∪A_2∪…∪A_{k+1}\right)=\underset{i=1}{\overset{k+1}{∑}}N\left(A_i\right)-\underset{i_1<i_2}{∑}N\left(A_{i_1}âˆ\copyright A_{i_2}\right)+…+(-1{)}^{r+1}\underset{i_1<…<i_r}{∑}N\left(A_{i_1}âˆ\copyright …âˆ\copyright A_{i_r}\right)+…+(-1{)}^{k+2}N\left(A_1âˆ\copyright …âˆ\copyright A_{k+1}\right)$

Hence we get the desired identity by mathematical induction.