ブールの不等式の証明と応用例

帰納法で証明する。$n=1$ のときは自明。

$n=k$ のとき正しいと仮定する。先述の公式を $A=A_1\cup\cdots \cup A_k,B=A_{k+1}$ として使うと，

$P(A_1\cup\cdots\cup A_{k+1})\\=P(A_1\cup\cdots\cup A_k)+P(A_{k+1})\\ -P((A_1\cup\cdots\cup A_k)\cap A_{k+1})$

ここで，帰納法の仮定より右辺第一項は $\displaystyle\sum_{t=1}^kP(A_t)$ 以下であることと，$P((A_1\cup\cdots\cup A_k)\cap A_{k+1})$ が非負であることから $n=k+1$ のときもブールの不等式は正しい。

$2n\log n$ 回引いても $k$ 番目の種類のガチャが一回も当たらない確率を $A_k$ とおく。

コンプリートできない確率は $P(A_1\cup \cdots\cup A_n)$ であるが，これはブールの不等式より $\displaystyle\sum_{k=1}^nP(A_k)=nP(A_1)$ 以下である。

ここで，

$P(A_1)=\left(\dfrac{n-1}{n}\right)^{2n\log n}\\ =\left\{\dfrac{1}{(1-\frac{1}{n})^{-n}}\right\}^{\log n^2}\\ \leq \dfrac{1}{e^{\log n^2}}\\ =\dfrac{1}{n^2}$

より主張は示された。