# 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}$. Commented Sep 21, 2019 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()$ Commented Sep 21, 2019 at 1:13
• yes exactly, ill correct it Commented Sep 21, 2019 at 1:17
• @user42493 I can't fathom why you would wait until adding that edit. We're not mind readers. Commented Sep 21, 2019 at 1:52
• :) :) :) indeed! I was just curious how you would solve it without knowing the formula! :):):) Commented Sep 21, 2019 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.

• I know in my gut that there is a natural, intuitive, motivated proof, but I'm too lazy to figure it out Commented Sep 21, 2019 at 12:02
• I hope so, too :D Commented Sep 21, 2019 at 12:22
• @DominikKutek Could you take a look at the expression $C_j = A_K \bigcap A_j$ . What does this mean? Commented Mar 14, 2021 at 15:34
• @DominikKutek You used $K$ to denote the subset of $\{1,\cdots,n\}$. Then what does $A_K$ mean here? Commented Mar 14, 2021 at 15:46
• when $T \subset \{1,..,n\}$ I defined $A_T = \bigcap_{j \in T} A_j$ (I defined it at the first paragraph of the answer) Commented Mar 14, 2021 at 16:40

Take the formula $$P(N_k)=\sum_{i=0}^{n-k}(-1)^i\binom{k+i}{k}S_{k+i}$$ and expand every term of form $$P(A_{i_1}\cap A_{i_2} \cap \dots \cap A_{i_p})$$ into a sum of probabilities of form $$P(X_1 \cap X_2 \cap \dots \cap X_n)$$ where $$X_i = A_i$$ or $$X_i = \overline{A_i}$$, according to the law of total probability.

Now consider some $$I = \{i_1, i_2, ..., i_m\} \subset \{1, ..., n\}$$ where $$k \leq m \leq n$$.

Let's consider probability that exactly events from $$I$$ have occured. What multiplier would it have in $$P(N_k)$$ ?

$$S_{k+i}$$ would contain this probability $$\binom{m}{k+i}$$ times.

So in $$P(N_k)$$ it would be equal to $$\sum_{i = 0}^{n - k} (-1)^i \binom{m}{k+i} \binom{k+i}{k} = \sum_{i = 0}^{n-k} (-1)^i \binom{m}{k}\binom{m-k}{i} = \binom{m}{k} \sum_{i=0}^{n-k}(-1)^i \binom{m-k}{i}$$

If $$m=k$$ then this equals $$1$$.

If $$k < m \le n$$ then this equals $$\binom{m}{k}(1 - 1)^{m-k} = 0$$

So $$P(N_k)$$ counts total probabilities when exactly $$k$$ events have occured, and counts such probabilities exactly once. QED