# 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

• It depends on how the $A_i$'s depend on one another. If there are $n$ fair coins that are each flipped and $A_i$ is the event that coin $i$ is heads, then the $A_i$'s are independent and $P(N_k) = {n \choose k}2^{-n}$. If there is a single fair coin flipped and each $A_i$ is the probability that the coin landed on heads, then $P(N_k) = 0$ for $1 \le k \le n-1$, $P(N_0) = \frac{1}{2}$, and $P(N_n) = \frac{1}{2}$. – mathworker21 Sep 21 at 0:34
• Shouldn't it be $S_j = \sum_{1 \le i_1 < ... < i_j \le n} \mathbb P ( \bigcap_{r=1}^j A_{i_r})$? Instead of that union under $\mathbb P()$ – Dominik Kutek Sep 21 at 1:13
• yes exactly, ill correct it – user 42493 Sep 21 at 1:17
• @user42493 I can't fathom why you would wait until adding that edit. We're not mind readers. – mathworker21 Sep 21 at 1:52
• :) :) :) indeed! I was just curious how you would solve it without knowing the formula! :):):) – user 42493 Sep 21 at 1:53

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.

• The proof isn't my own, I've just recall and modify a little bit proof I've seen once, about combinatorial identity. The most "tricky" part for me is to come up with these disjoint events $B_K$. – Dominik Kutek Sep 21 at 2:05
• I know in my gut that there is a natural, intuitive, motivated proof, but I'm too lazy to figure it out – mathworker21 Sep 21 at 12:02
• I hope so, too :D – Dominik Kutek Sep 21 at 12:22