418531 ภาคต้น 2552/โจทย์ปัญหาความน่าจะเป็น I/เฉลยข้อ 8

เราจะพิสูจน์ข้อความในโจทย์ด้วย induction บน $n\,$

(Base Case) $n\,$ มีค่าเท่ากับ 1 เราได้ว่า $\Pr(E_{1})\geq \Pr(E_{1})-(1-1)$

(Induction Case) สมมติให้ข้อความในโจทย์เป็นจริง ให้ $E_{1},E_{2},\ldots ,E_{n},E_{n+1}\,$ เป็นเหตุการณ์ใดๆ

เราได้ว่า

$\Pr(E_{1}\cap E_{2}\cap \dotsb \cap E_{n}\cap E_{n+1})\,$	$=\,$	$1-\Pr({\overline {E_{1}\cap E_{2}\cap \dotsb \cap E_{n}\cap E_{n+1}}})\,$
	$=\,$	$1-\Pr({\overline {E_{1}}}\cup {\overline {E_{2}}}\cup \dotsb \cup {\overline {E_{n}}}\cup {\overline {E_{n+1}}})\,$
	$\geq \,$	$1-\Pr({\overline {E_{1}}}\cup {\overline {E_{2}}}\cup \dotsb \cup {\overline {E_{n}}})-\Pr({\overline {E_{n+1}}})\,$	เหตุผล: โดย union bound เราได้ว่า $\Pr({\overline {E_{1}}}\cup {\overline {E_{2}}}\cup \dotsb \cup {\overline {E_{n}}}\cup {\overline {E_{n+1}}})\leq \Pr({\overline {E_{1}}}\cup {\overline {E_{2}}}\cup \dotsb \cup {\overline {E_{n}}})+\Pr({\overline {E_{n+1}}})\,$
	$=\,$	$1-\Pr({\overline {E_{1}\cap E_{2}\cap \dotsb \cap E_{n}}})-1+\Pr(E_{n+1})\,$
	$=\,$	$\Pr(E_{1}\cap E_{2}\cap \dotsb \cap E_{n})-1+\Pr(E_{n+1})\,$
	$\geq \,$	$\Pr(E_{1})+\Pr(E_{2})+\dotsb +\Pr(E_{n})-(n-1)-1+\Pr(E_{n+1})\,$	ด้วยสมมติฐานของ induction
	$=\,$	$\Pr(E_{1})+\Pr(E_{2})+\dotsb +\Pr(E_{n+1})-n\,$

ฉะนั้นเราสามารถสรุปได้ว่าข้อความในโจทย์เป็นจริงสำหรับจำนวนเต็มบวก $n\,$ ทุกจำนวน