Please help to complete proof of inclusion and exclusion principle

Question

I want to complete the following proof:

So continuing where the author left off, I did the following:

$\begin{array} {cc} & \sum\limits_{i=1}^{n-1} P(A_i) - \sum\limits_{1\le i < j \le n-1}P(A_i \cap A_j) + \dots + (-1)^n P(A_1 \cap A_2 \cap \dots \cap A_{n-1}) + P(A_n) - P(\bigcup\limits_{i=1}^{n-1} (A_i \cap A_n))\\ &= \sum\limits_{i=1}^{n-1} P(A_i) - \sum\limits_{1\le i < j \le n-1}P(A_i \cap A_j) + \dots + (-1)^n P(A_1 \cap A_2 \cap \dots \cap A_{n-1}) + P(A_n) - \left[ \sum\limits_{i=1}^{n-1}P(A_i \cap A_n) - \sum\limits_{1\leq i < j \leq n-1}^{n-1}P(A_i \cap A_j \cap A_n) + \dots + (-1)^nP(A_i \cap A_2 \cap \dots \cap A_{n-1}\cap A_n)\right]\\ \end{array}$

I got here by applying the inclusion exclusion formula to $P(\bigcup\limits_{i=1}^{n-1} (A_i \cap A_n)$ as the author instructed and then simplyfying based on the following:

$(A_i \cap A_n) \cap (A_j \cap A_n) = A_i \cap A_j \cap A_n$

I tried this new formula with $n=3$ and I did get the correct answer, so I think that the manipulations I did is correct.

Also, I know I can get the $\sum\limits_{i=1}^{n}P(A_i)$ in the theorem because:

$\sum\limits_{i=1}^{n}P(A_i) = \sum\limits_{i=1}^{n-1}P(A_i) + P(A_n)$

So, this formula can be simplified to:

$\sum\limits_{i=1}^{n} P(A_i) - \sum\limits_{1\le i < j \le n-1}P(A_i \cap A_j) + \dots + (-1)^n P(A_1 \cap A_2 \cap \dots \cap A_{n-1}) - \left[ \sum\limits_{i=1}^{n-1}P(A_i \cap A_n) - \sum\limits_{1\leq i < j \leq n-1}^{n-1}P(A_i \cap A_j \cap A_n) + \dots + (-1)^nP(A_i \cap A_2 \cap \dots \cap A_{n-1}\cap A_n)\right]$

Now I don't know how to proceed.

If the answer involves manipulating the summations then the more detailed the answer, the better as I am not too familiar with manipulating sums.

Answer 1

In the first line of your last equation, you have the term $-\sum_{1\leq i < j\leq n-1} P(A_i\cap A_j)$. In the inclusion-exclusion formula, you have to subtract all $P(A_i\cap A_j)$ for $1\leq i<j\leq n$. Hence, you are missing here all the terms of the form $P(A_i\cap A_n)$ for $1\leq i < n$. But note now that those terms are in your second line, so you can regroup them to get the desired $-\sum_{1\leq i<j\leq n} P(A_i\cap A_j)$.

The next term that should appear on your first line (and that you abbreviated with the dots), is $\sum_{1\leq i < j < k \leq n-1} P(A_i\cap A_j\cap A_k)$. As before, in the inclusion-exclusion principle, you'd have to have $\sum_{1 \leq i < j < k \leq n} P(A_i\cap A_j \cap A_k)$, do you see the difference? Again, you are missing the terms of the form $P(A_i\cap A_j\cap A_n)$ for $1\leq i < j < n$, and again, those appear in the second line, hence you can regroup to obtain the term of the inclusion-exclusion formula.

I hope you now get the pattern. Each time with the induction hypothesis on the first line you obtained a formula for which some terms are missing, but the missing terms come from the second line (and the very last term missing comes from the third line), hence you regroup and you are done. This proof can be made more "formal" by writing it with summations, but I think its clearer this way.