vollständige Induktion < Stochastik < Hochschule < Mathe < Vorhilfe
|
Hi Leute,
Ich habe hier eine knifflige Aufgabe, wo ich bei einem Schritt überhaupt nicht weiterkomme (und morgen ist schon Abgabe):
Aufgabe:
Weise nach, daß [mm] $\forall [/mm] n [mm] \in \IN$ [/mm] und jede Folge [mm] $A_1,\ldots,A_n$ [/mm] von Ereignissen folgendes gilt:
[m]P\left( {\bigcup\limits_{i = 1}^n {A_i } } \right) = \sum\limits_{i = 1}^n {\left( { - 1} \right)^{i - 1} \sum\limits_{1 \leqslant k_1 < \cdots < k_i \leqslant n} {P\left( {A_{k_1 } \cap \cdots \cap A_{k_i } } \right)} }[/m]
Lösungsansatz:
Ich habe es also mit vollständiger Induktion über n versucht:
Induktionsanfang (n = 1):
[m]P\left( {\bigcup\limits_{i = 1}^1 {A_i } } \right) = P\left( {A_1 } \right) = P\left( {A_{k_1 = 1} } \right) = \sum\limits_{1 \leqslant k_1 \leqslant 1} {P\left( {A_{k_1 } } \right)} = \sum\limits_{i = 1}^1 {\underbrace {\left( { - 1} \right)^{i - 1} }_{\begin{subarray}{l}
{\text{hier:}} \\
= \left( { - 1} \right)^0 = 1
\end{subarray}} \sum\limits_{1 \leqslant k_1 \leqslant 1} {P\left( {A_{k_1 } } \right)} }[/m]
Induktionsannahme:
Angenommen die zu beweisende Aussage wäre wahr [mm] $\forall [/mm] n [mm] \in \IN$.
[/mm]
Induktionsschritt (n --> n+1):
[m]\begin{gathered}
P\left( {\bigcup\limits_{i = 1}^{n + 1} {A_i } } \right) = P\left( {\left( {\bigcup\limits_{i = 1}^n {A_i } } \right) \cup A_{n + 1} } \right) = P\left( {\bigcup\limits_{i = 1}^n {A_i } } \right) + P\left( {A_{n + 1} } \right) - P\left( {\left( {\bigcup\limits_{i = 1}^n {A_i } } \right) \cap A_{n + 1} } \right) \hfill \\
\mathop = \limits^{{\text{I}}{\text{.A}}{\text{.}}} \left( {\sum\limits_{i = 1}^n {\left( { - 1} \right)^{i - 1} \sum\limits_{1 \leqslant k_1 < \cdots < k_i \leqslant n} {P\left( {A_{k_1 } \cap \cdots \cap A_{k_i } } \right)} } } \right) + \underbrace {P\left( {A_{n + 1} } \right) - P\left( {\left( {\bigcup\limits_{i = 1}^n {A_i } } \right) \cap A_{n + 1} } \right)}_{ = P\left( {A_{n + 1} \backslash \bigcup\limits_{i = 1}^n {A_i } } \right) = P\left( {\left( {\bigcup\limits_{i = 1}^n {A_i } } \right)^c \cap A_{n + 1} } \right) = P\left( {\bigcap\limits_{i = 1}^n {A_i^c } \cap A_{n + 1} } \right) = ?} = ? \hfill \\
\end{gathered}[/m]
Und hier komme ich nun nicht weiter. Ich will am Ende ja auf folgenden Summanden kommen:
[m]\left( { - 1} \right)^n \sum\limits_{1 \leqslant k_1 < \cdots < k_i \leqslant n + 1} {P\left( {A_{k_1 } \cap \cdots \cap A_{k_i } } \right)}[/m]
Wenn ich diese Umformung schaffe, wäre die Induktion vollständig.
Wäre Klasse, wenn ihr mir da etwas helfen könntet. 
Vielen Dank!
Grüße
Karl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:53 Di 03.05.2005 | | Autor: | Micha |
Hallo!
Also das ist der Beweis zur Formel von Sylvester. Ich schreibe dir mal den endgültigen Beweis aus meinem Skript auf. Der Ansatz war sehr richtig.
>
> Lösungsansatz:
>
> Ich habe es also mit vollständiger Induktion über n
> versucht:
>
> Induktionsanfang (n = 1):
>
> [m]P\left( {\bigcup\limits_{i = 1}^1 {A_i } } \right) = P\left( {A_1 } \right) = P\left( {A_{k_1 = 1} } \right) = \sum\limits_{1 \leqslant k_1 \leqslant 1} {P\left( {A_{k_1 } } \right)} = \sum\limits_{i = 1}^1 {\underbrace {\left( { - 1} \right)^{i - 1} }_{\begin{subarray}{l}
> {\text{hier:}} \\
> = \left( { - 1} \right)^0 = 1
> \end{subarray}} \sum\limits_{1 \leqslant k_1 \leqslant 1} {P\left( {A_{k_1 } } \right)} }[/m]
>
> Induktionsannahme:
>
> Angenommen die zu beweisende Aussage wäre wahr [mm]\forall n \in \IN[/mm].
>
> Induktionsschritt (n --> n+1):
>
> [m]\begin{gathered}
> P\left( {\bigcup\limits_{i = 1}^{n + 1} {A_i } } \right) = P\left( {\left( {\bigcup\limits_{i = 1}^n {A_i } } \right) \cup A_{n + 1} } \right) = P\left( {\bigcup\limits_{i = 1}^n {A_i } } \right) + P\left( {A_{n + 1} } \right) - P\left( {\left( {\bigcup\limits_{i = 1}^n {A_i } } \right) \cap A_{n + 1} } \right) \hfill \\
> \mathop = \limits^{{\text{I}}{\text{.A}}{\text{.}}} \left( {\sum\limits_{i = 1}^n {\left( { - 1} \right)^{i - 1} \sum\limits_{1 \leqslant k_1 < \cdots < k_i \leqslant n} {P\left( {A_{k_1 } \cap \cdots \cap A_{k_i } } \right)} } } \right) + \underbrace {P\left( {A_{n + 1} } \right) - P\left( {\left( {\bigcup\limits_{i = 1}^n {A_i } } \right) \cap A_{n + 1} } \right)}_{ = P\left( {A_{n + 1} \backslash \bigcup\limits_{i = 1}^n {A_i } } \right) = P\left( {\left( {\bigcup\limits_{i = 1}^n {A_i } } \right)^c \cap A_{n + 1} } \right) = P\left( {\bigcap\limits_{i = 1}^n {A_i^c } \cap A_{n + 1} } \right) = ?} = ? \hfill \\
> \end{gathered}[/m]
Hier der Induktionsschritt aus meinem Skript:
[mm] P \left( \bigcup\limits_{i=1}^{n+1} A_i \right) = ... = \ {\sum\limits_{i = 1}^n {\left( { - 1} \right)^{i - 1} \sum\limits_{1 \leqslant k_1 < \cdots < k_i \leqslant n} {P\left( {A_{k_1 } \cap \cdots \cap A_{k_i } } \right)} } } + P\left( {A_{n + 1} } \right) - P\left( { {\bigcup\limits_{i = 1}^n \left( {A_i } \cap A_{n + 1} \right)} } \right) [/mm]
= [m]\left( { - 1} \right)^n \sum\limits_{1 \leqslant k_1 < \cdots < k_i \leqslant n + 1} {P\left( {A_{k_1 } \cap \cdots \cap A_{k_i } } \right)}[/m]
Als Begründung steht dazu: Die Gültigkeit der letzten Gleichheit erkennt man, wenn man die letzte Summe in zwei Teilsummen aufspaltet, indem man einmal über [mm] 1 \le k_1 < ... < k_i \le n [/mm] summiert und zum anderen die Summe über alle Indizes mit [mm] 1 \le k_1 < ... < k_{i-1} < k_i = n+1 [/mm] erstreckt und anschließend im zweiten Teil eine Indexverscheibung von i um 1 durchführt...
Vielleicht hilft es dir ja...
Viel Erfolg bei der Abgabe!
Gruß Micha
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 21:25 Do 22.02.2007 | | Autor: | Riley |
Hallo!
Kann mir jemand diesen letzten schritt erklären, wie man das genau zusammenfassen muss?
also bis hierher ist klar, aber dann??
[mm] \left( \bigcup\limits_{i=1}^{n+1} A_i \right) [/mm] = ... = \ [mm] {\sum\limits_{i = 1}^n {\left( { - 1} \right)^{i - 1} \sum\limits_{1 \leqslant k_1 < \cdots < k_i \leqslant n} {P\left( {A_{k_1 } \cap \cdots \cap A_{k_i } } \right)} } } [/mm] + [mm] P\left( {A_{n + 1} } \right) [/mm] - [mm] P\left( { {\bigcup\limits_{i = 1}^n \left( {A_i } \cap A_{n + 1} \right)} } \right)
[/mm]
viele grüße
riley
edit: auch hier gefragt: www.matheboard.de
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 Mo 26.02.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
