proof of Waring's theorem So the question is that if we have a sequence $A_1,A_2,...,A_n$ of events, and let $N_k$ be the events that exactly $k$ of the $A_i$ occur. What is the probability of event $N_k$?
Prove that it is $P(N_k)=\sum_{i=0}^{n-k}(-1)^i\binom{k+i}{k}S_{k+i} $ where $S_j=\sum_{i_1<i_2<...<i_j}P(A_{i_1}\cap A_{i_2} \cap...\cap A_{i_n})$
 A: So, we have probability space $(\Omega, \mathcal F, \mathbb P)$, and let $A_1,...,A_n \in \mathcal F$ be arbitrary events. I'd change notation, especially $k$ with $r$ because I like to use $k$ as an index under $\sum$ sign. So let's fix any $r \in \{1, ... ,n\}$ and let $N_r \in \mathcal F$ be event : Exactly $r$ of $A_1,...,A_n$ occurs. Let $S_k(n) = \{ T \subset \{1,...,n\} : |T| = k \} $ ($k-$ element subsets of $\{1,...,n\}$. Finally for $T \subset \{1,...,n\}$ let $A_T = \bigcap_{ j \in T} A_j $
We'd like to prove (I've translated the index of sum): $$\mathbb P(N_r) = \sum_{k=r}^n (-1)^{k-r} {k \choose r} \sum_{T \in S_k(n)}\mathbb P(A_T)$$
PROOF:
Fix any $K \in S_r(n)$. Let $B_K$ be the event: $A_i$ occur if and only if $i \in K$ ( that is exactly $r$ of $A_1 ,... ,A_n$ occured and only those with indices from $K$). Now, for $j \notin K$ let $C_j = A_K \cap A_j$. We're interested in $\mathbb P(B_K)$. Note that we can now use Inclusion-Exclusion formula, because $\mathbb P(B_K) = \mathbb P( \bigcap_{j \notin K} (A_K \setminus C_j)) $. To remind, set $K$ is fixed, and there is exactly $n-r$ indices in $L = [n]\setminus K$, where $[n] = \{1,...,n\}$ And again let $C_T = \bigcap_{j \in T} C_j$, where $T \subset [n]$
Using Inclusion-Exclusion, we have:
$$ \mathbb P(B_K) = \sum_{k=0}^{n-r} (-1)^k  \sum_{T \in S_k(L)} \mathbb P(C_T) = \sum_{k=0}^{n-r} (-1)^k \sum_{T \in S_k(L)} \mathbb P( A_K \cap A_T) = \sum_{k=0}^{n-r} (-1)^k \sum_{T \in S_k(L)} \mathbb P(A_{T \cup K}) = \sum_{k=r}^n \sum_{T: K \subset T, T \in S_k(n)} (-1)^{k-r} \mathbb P(A_T) = \sum_{T: K \subset T \subset [n]} (-1)^{|T|-r} \mathbb P(A_T)$$
Now what we need to do, is to sum it for every $K \in S_r(n)$ (note $B_{K_1}, B_{K_2}$ are disjoint for any $K_1 \neq K_2$)
And we have:
$$ \mathbb P(N_r) = \mathbb P(\bigcup_{K \in S_r(n)} B_K) =  \sum_{K \in S_r(n)}\mathbb P(B_K) =\sum_{K \in S_r(n)}\sum_{T: K \subset T \subset [n]} (-1)^{|T|-r} \mathbb P(A_T) = \sum_{T: |T| \ge r} \sum_{R \in S_r(T)} (-1)^{|T|-r} \mathbb P(A_T) = \sum_{T: |T| \ge r} {|T| \choose r} (-1)^{|T| - r} \mathbb P(A_T) = \sum_{k=r}^n \sum_{T \in S_k(n)} {k \choose r} (-1)^{k-r} \mathbb P(A_T) = \sum_{k=r}^n (-1)^{k-r} {k \choose r} \sum_{T \in S_k(n)} \mathbb P(A_T)  $$
Which is exactly what we wanted to prove.
