容斥恒等式的证明

容斥恒等式的证明

推广公式
$$P(A\cup B)=P(A)+P(B)-P(A\cap B)$$
(a)设A、B、C为三个事件，则下列恒等式成立：
$$P(A\cup B\cup C)=P(A)+P(B)+P(C)-P(A\cap B)-P(A\cap C)-P(B\cap C)+P(A\cap B\cap C)$$
(b)设$A_1$,$A_2$,$A_3$,…,$A_n$为n个事件，令$S_1$={$i|1\le i\le n$},$S_2$={$(i_1,i_2)|1\le i_1<i_2\le n$},一般的，令$S_1$为满足条件$ \le i_1 < i_2<… < i_m\le n$的m维指标，($i_1,…i_m$)的集合，则下列恒等式成立：
$P({\cup }_{k=1}^n{A}_k)=\sum _{i\in S_1}P(A_i)-\sum _{(i_1,i_2)\in S_2}P(A_{i_1}\cap A_{i_2})+\sum _{i_1,i_2,i_3\in S_3}P(A_{i_1}\cap A_{i_2}\cap A_{i_3})-...+(-1{)}^{n-1}P({\cap }_{k=1}^n{A}_k)$

解：(a)利用公式$P(X\cup Y)=P(X)+P(Y)-P(X\cap Y)$和$(A\cup B)\cap C=(A\cap C)\cup (B\cap C)$,我们有
$$\begin{gathered} P(A\cup B\cup C)=P(A\cup B)+P(C)-P((A\cup B)\cap C) \\ =P(A\cup B)+P(C)-P((A\cap C)\cup (B\cap C)) \\ =P(A\cup B)+P(C)-P(A\cap C)-P(B\cap C)+P(A\cap B\cap C) \\ =P(A)+P(B)-P(A\cap B)+P(C)-P(A\cap C)-P(B\cap C)+P(A\cap B\cap C) \\ =P(A)+P(B)+P(C)-P(A\cap B)-P(A\cap C)-P(B\cap C)+P(A\cap B\cap C) \end{gathered}$$
(b)利用归纳法，主要推断部分可以模仿(a)中步骤

n=2时，$P(A\cup B)=P(A)+P(B)-P(A\cap B)$.

假设n=k-1,有
$P({\cup }_{k=1}^{k-1}{A}_k)=\sum _{i\in S_1}P(A_i)-\sum _{(i_1,i_2)\in S_2}P(A_{i_1}\cap A_{i_2})+\sum _{i_1,i_2,i_3\in S_3}P(A_{i_1}\cap A_{i_2}\cap A_{i_3})-...+(-1{)}^{n-2}P({\cap }_{k=1}^{k-1}{A}_{i_k})$

则n=k时，$P({\cup }_{k=1}^n{A}_k)=P({\cup }_{k=1}^{k-1}{A}_k\cup A_k)$

令${\cup }_{i=1}^{k-1}{A}_i=B$,

$P({\cup }_{k=1}^n{A}_k)=P(B\cup A_k)$
所以，

$P({\cup }_{k=1}^n{A}_k)=P(B\cup A_k)=P(B)+P(A_k)-P(B\cap A_k)$ （1）

前两个地方都很好推导，主要是最后一项。

$$\begin{gathered} P(B\cap A_k)=P({\cup }_{i=1}^{k-1}{A}_i{A}_k) \\ =\sum _{i=1}^{k-1}P(A_i{A}_k)+(-1^1)\sum _{1\le i_1<i_2\le i_{k-1}}P(A_{i_1}{A}_{i_2}{A}_k)+...+(-1{)}^{k-2}P(A_1{A}_2...A_k) \end{gathered}$$ （2）

把（2）带入（1），

得到：

$P({\cup }_{k=1}^n{A}_k)=\sum _{i\in S_1}P(A_i)-\sum _{(i_1,i_2)\in S_2}P(A_{i_1}\cap A_{i_2})+\sum _{i_1,i_2,i_3\in S_3}P(A_{i_1}\cap A_{i_2}\cap A_{i_3})-...+(-1{)}^{n-1}P({\cap }_{k=1}^n{A}_k)$

得证。