# the proof of Waring's theorem in Probability and Random process by Grimmett and Stirzaker

Let $$A_1, A_2, ... , A_n$$ be events and let $$N_k$$ be the event that exactly $$k$$ of the $$A_i$$ occur. Prove the result sometimes referred to as Waring's theorem:

$$P(N_k) = \sum_{i=0}^{n-k} (-1)^i {k+i \choose k}S_{k+i}, \text{where S_j = \sum_{i_1 < i_2 < ...

Solution: Clearly, $$P(N_k) = \sum_{S \subseteq \{1,2, ... , n\};|S| = k} P\left(\bigcap_{i \in S} A_i \bigcap_{j \not\in S} A_j^c \right).$$ For any such given $$S$$, we write $$A_S = \bigcap_{i\in S}A_i$$. Then, $$$$P\left(\bigcap_{i \in S} A_i \bigcap_{j \not\in S} A_j^c \right) = P(A_S) - \sum_{j \not\in S} P(A_{S \cup \{j\}})+ \sum_{j Hence $$P(N_k) = \sum_{|S| = k} P(A_S) -\sum_{|S| = k+1}{k+1 \choose k}P(A_S)+ ... + (-1)^{n-k}{n \choose k} P(A_1 \cap ... \cap A_n)$$ where a typical summation is over all subsets $$S$$ of $$\{1, 2, ..., n\}$$ having the required cardinality.

I am not sure how the author derives the last and the second last display in the solution. I guess he uses the previous results that

$$P\left(\bigcap_{1}^n A_i \right) = \sum_i P(A_i) - \sum_{i < j} P(A_i \cup A_j) + \sum_{i < j or similarly, $$P\left(\bigcup_{1}^n A_i \right) = \sum_i P(A_i) - \sum_{i < j} P(A_i \cap A_j) + \sum_{i < j in some way, but I can't figure it out by myself. I appreciate if you give some help.

• Does $P\left((\bigcap_{i \in S} A_i \bigcap_{j \not\in S} A_j^c \right)$ mean $P\left(\bigcap_{i \in S} A_i ) \bigcap (\bigcap_{j \not\in S} A_j^c \right)).$ ?? Commented Mar 14, 2021 at 15:44

For the second last display, write \begin{align} P\left(A_S\bigcap A_j^c\right) = P\left(A_S\cap\left(\bigcup A_j\right)^c\right) &\stackrel{(*)}=P(A_S)-P\left(A_S\cap \left(\bigcup A_j\right)\right)\\ &=P(A_S)-P\left(\bigcup (A_S\cap A_j)\right) \end{align} and then use inclusion-exclusion on the rightmost union (which is a union over $$j\not\in S$$). The equality (*) is the identity $$P(A\cap B^c)=P(A)-P(A\cap B)$$.
For the last display, we sum every term of the previous display over all subsets $$S$$ with $$|S|=k$$. The first term that we get (the one with $$|S|=k$$) is obvious. For the second term, the assertion is that $$\sum_{|S|=k}\sum_{j \not\in S} P(A_{S \cup \{j\}})=\sum_{|S|=k+1}{k+1\choose k}P(A_S).$$ The reason this is true: the LHS is selecting a subset $$S$$ of size $$k$$ and then, given $$S$$, selecting an element $$j$$ not in $$S$$. The RHS is selecting a subset of size $$k+1$$ and then choosing an element from that subset to be $$j$$. There are clearly $$k+1\choose k$$ ways to pick $$j$$, so the RHS achieves the same sum as the LHS. The remaining terms are argued similarly.
• Does $P\left((\bigcap_{i \in S} A_i \bigcap_{j \not\in S} A_j^c \right)$ mean $P\left(\bigcap_{i \in S} A_i ) \bigcap (\bigcap_{j \not\in S} A_j^c \right)).$ ?? Commented Mar 14, 2021 at 15:41
• Yes, the middle $\cap$ is implied between $\bigcap_{i\in S}A_i$ and $\bigcap_{j\not\in S}A_j^c$. Commented Mar 14, 2021 at 22:30