Beweis über Induktion

Question

folgende Aufgabe:

Ich muss nun für A1, . . . , An ∈ A mit vollständiger Induktion zeigen, dass:

Text erkannt:

$\mathbb{P}\left(\bigcup_{i=1}^{n} A_{i}\right)=\sum \limits_{r=1}^{n}(-1)^{r+1} \sum \limits_{1 \leq i_{1}<\cdots<i_{r} \leq n} \mathbb{P}\left(\bigcap_{j=1}^{r} A_{i_{j}}\right)$.

gilt.

Ich finde leider meinen Ansatz nicht und würde mich über jede Hilfe freuen.

BG

Answer 1

Im Fall n=2 könen wir die beteiligten Mengen disjunkt zerlegen

$$A=(A \cap B) \cup (A \setminus B), \quad B=(A \cap B) \cup (B \setminus A)$$

und berechnen

$$P(A \cup B)=P(A \cap B) + P(A \setminus B)+P(B \setminus A)=P(A)+P(B)-P(A \cap B)$$

Nun gelte für ein $n\geq 2$ die Formel für beliebige Mengen. D.h.

$$P(\bigcup_{i=1}^nA_i)=\sum_{(r,I)}(-1)^{r+1}P(M(I))\\ \text{ mit } r=1, \ldots,n, I \sub\{1, \ldots n\},|I|\leq r, M(I):=\bigcap_{j \in I}A_j$$

(Ich habe es umformuliert, weil mir das so einfacher erscheint.)

Für die Induktionsbehauptung verwenden wir zunächst die Formel für n=2, dann die Induktionsvoraussetzung:

$$P(\bigcup_{i=1}^{n+1}A_i)=P(\bigcup_{i=1}^nA_i)+P(A_{n+1})-P((\bigcup_{i=1}^nA_i) \cap A_{n+1})\\\quad =\sum_{(r,I)}(-1)^{r+1}P(M(I))+P(A_{n+1})-P((\bigcup_{i=1}^nA_i) \cap A_{n+1})$$

Im Hinblick auf die Induktionsbehauptung liefert dieser Term zunächst für r=1 zusammen mit dem einzelnen Summanden:

$$\text{BEITRAG 1}\quad \sum_{i=1}^{n+1}P(A_i)$$

Die weiteren Terme der ersten Summe notieren wir als

$$\text{BEITRAG 2}\quad \sum_{(r,I)}(-1)^{r+1}P(M(I)), \text{ mit } r=2, \ldots n, I \sub \{1,\ldots n+1\},n+1 \notin I,|I|\leq r$$

Für den dritten Term benutzen wir nochmal die Induktionsvoraussetzung:

$$-P((\bigcup_{i=1}^nA_i) \cap A_{n+1})=-P(\bigcup_{i=1}^n(A_i \cap A_{n+1})) \\ \quad=\sum_{(r,I)}(-1)^rP(\bigcap_{j \in I}(A_j \cap A_{n+1}))\text{ mit } r=1, \ldots,n, I \sub\{1, \ldots n\},|I|\leq r$$

Dies ist aber

$$\text{BEITRAG 3}\quad \sum_{(r,I)}(-1)^{r+1}P(M(I)) \text{ mit }r=2,\ldots,n+1, I \sub \{1, \ldots , n+1\},n+1 \in I,|I|\leq r$$

Die drei Beiträge zusammen liefern die Behauptung.