Umkehrformel

14.11.2019, 16:01

Tino11

Umkehrformel

Meine Frage:
Hallo,
ich brauche eure Hilfe bei der folgenden Aufgabe:

Meine Ideen:
Leider weiß ich gar nicht worum es hier geht und wie ich vorgehen soll.

edit Mathema: Es fehlt folgender Satz: Ich habe die Frage auch hier gestellt.
Siehe dazu Punkt 3 in Prinzip "Mathe online verstehen!"
Wenn du gute Manieren hast, solltest du das übrigens in deinem anderen Thread auch erwähnen. Beim nächsten Mal schließe ich hier direkt. Vielen Dank für das Verständnis!

14.11.2019, 18:06

HAL 9000

Auf diesen Beitrag antworten »

Ich würde Induktion über $\begin{eqnarray*} |T| \end{eqnarray*}$ vorschlagen. Genauer gesagt beweist man da die Äquivalenz von

$\begin{eqnarray*} (a_n) \end{eqnarray*}$ : Für alle $\begin{eqnarray*} T\subset M \end{eqnarray*}$ mit $\begin{eqnarray*} |T|\leq n \end{eqnarray*}$ gilt $\begin{eqnarray*} g(T) = \sum_{S\subset T} f(S) \end{eqnarray*}$ .

mit

$\begin{eqnarray*} (b_n) \end{eqnarray*}$ : Für alle $\begin{eqnarray*} T\subset M \end{eqnarray*}$ mit $\begin{eqnarray*} |T|\leq n \end{eqnarray*}$ gilt $\begin{eqnarray*} f(T) = \sum_{S\subset T} (-1)^{\left|T\setminus S\right|} g(S) \end{eqnarray*}$ .

per Vollständiger Induktion über $\begin{eqnarray*} n \end{eqnarray*}$ .

Aber bevor wir damit loslegen solltest du die Aussage erstmal inhaltlich voll erfassen - daran scheint es noch zu hapern, wenn ich den anderen Thread richtig verstanden habe.

Hier aber schon mal eine kleine Nebenrechnung, die im eigentlichen Induktionsschritt eine wichtige Bedeutung haben wird: Für $\begin{eqnarray*} U\subsetneq T \end{eqnarray*}$ gilt mit $\begin{eqnarray*} m:=\left|T\setminus U\right| \end{eqnarray*}$ die Gleichung

$\begin{eqnarray*} \sum_{S:\;U\subset S\subset T} (-1)^{\left|S\setminus U\right|} = \sum_{S'\subset (T\setminus U)} (-1)^{\left|S'\right|} = \sum_{k=0}^{m} \binom{m}{k} (-1)^k = (1-1)^m = 0 \end{eqnarray*}$ ,

und damit nach Entfernung der "größten" Summandenmenge $\begin{eqnarray*} S=T \end{eqnarray*}$ :

$\begin{eqnarray*} \sum_{S:\;U\subset S\subsetneq T} (-1)^{\left|S\setminus U\right|} = - (-1)^{\left|T\setminus U\right|} \end{eqnarray*}$ .

14.11.2019, 19:16

Tino11

Auf diesen Beitrag antworten »

Inzwischen habe ich die Formel verstanden, aber wie führt man genau den Beweis hier? Magst du mir den vollständigen Beweis zeigen? Morgen ist leider Abgabe...

14.11.2019, 20:30

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Tino11
Inzwischen habe ich die Formel verstanden

Da bin ich gespannt, ob das stimmt. Der Induktionsanfang wäre hier $\begin{eqnarray*} n=0 \end{eqnarray*}$ : Was ist für den hier zu zeigen? Und führe das am besten gleich mal durch.

14.11.2019, 21:26

Tino11

Auf diesen Beitrag antworten »

Für den Induktionsanfang n=0 gilt:
$\begin{eqnarray*} a_{n} \end{eqnarray*}$ : Für alle $\begin{eqnarray*} T \in M \end{eqnarray*}$ mit $\begin{eqnarray*} |T| \leq 0 \end{eqnarray*}$ gilt $\begin{eqnarray*} g(0)=\sum\limits_{0 \subset 0} f(0) \end{eqnarray*}$
$\begin{eqnarray*} b_{n} \end{eqnarray*}$ : Für alle $\begin{eqnarray*} T \in M \end{eqnarray*}$ mit $\begin{eqnarray*} f(0)=\sum\limits_{0 \subset 0} (-1)^{|T| \backslash S} g(0) \end{eqnarray*}$
Ich schätze, man soll hier zeigen, dass es auch für n+1 gilt, aber wie beweist man das mit Induktion?
Bitte helft mir, wenn ihr könnt, ich habe leider nicht mehr viel Zeit vor der Abgabe.

14.11.2019, 21:39

HAL 9000

Auf diesen Beitrag antworten »

Da es nur eine Teilmenge $\begin{eqnarray*} T \end{eqnarray*}$ mit $\begin{eqnarray*} |T|\leq 0 \end{eqnarray*}$ gibt, nämlich die leere Menge $\begin{eqnarray*} T=\emptyset \end{eqnarray*}$ , und dieses $\begin{eqnarray*} T \end{eqnarray*}$ auch nur eine Teilmenge $\begin{eqnarray*} S \end{eqnarray*}$ hat, nämlich ebenfalls $\begin{eqnarray*} S=\emptyset \end{eqnarray*}$ , lauten die beiden Aussagen brauchbar (!) vereinfacht

$\begin{eqnarray*} (a_0) \end{eqnarray*}$ : Es gilt $\begin{eqnarray*} g(\emptyset) = f(\emptyset) \end{eqnarray*}$ .

$\begin{eqnarray*} (b_0) \end{eqnarray*}$ : Es gilt $\begin{eqnarray*} f(\emptyset) = g(\emptyset) \end{eqnarray*}$ .

Und dass diese beiden Aussagen äquivalent sind, ist ja wohl offensichtlich. Mehr ist nicht zu tun im Induktionsanfang.

Da du nicht mal das allein hingekriegt hast, wie willst du dann den deutlich komplizierteren Induktionsschritt verstehen? Und dann war ja noch das:

Zitat:

edit Mathema: [...]Wenn du gute Manieren hast, solltest du das übrigens in deinem anderen Thread auch erwähnen.

Ist auch bis jetzt nicht geschehen. Stattdessen lese ich auf

https://www.matheplanet.com/default3.htm...hp?topic=244362

dieselbe Zeitnot-Bettelei wie hier. Ich verspüre momentan wenig Motivation, heute abend hier noch weiter zu machen. unglücklich

14.11.2019, 21:44

Tino11

Auf diesen Beitrag antworten »

Den Induktionsanfang verstehe ich ja noch, aber wie lautet der Induktionsschritt? Was soll ich machen, wenn ich einfach nicht selber die Aufgabe schaffe? Wenn mir jemand die Lösung verrät, dann hätte ich noch die Möglichkeit das nachzuvollziehen.

15.11.2019, 09:39

HAL 9000

Auf diesen Beitrag antworten »

Der Induktionsschritt $\begin{eqnarray*} (n-1)\to n \end{eqnarray*}$ besteht aus dem Nachweis zweier Implikationen:

1. $\begin{eqnarray*} (a_n)\Rightarrow (b_n) \end{eqnarray*}$ :

Wir müssen nachweisen $\begin{eqnarray*} f(T) = \sum_{S\subset T} (-1)^{\left|T\setminus S\right|} g(S) \end{eqnarray*}$ für alle $\begin{eqnarray*} T \end{eqnarray*}$ mit $\begin{eqnarray*} |T|\leq n \end{eqnarray*}$ . Für $\begin{eqnarray*} |T|<n \end{eqnarray*}$ ist das bereits per Induktionsvoraussetzung erledigt, es geht daher im folgenden nur um $\begin{eqnarray*} |T|=n \end{eqnarray*}$ . Betrachten wir nun ein solches $\begin{eqnarray*} T \end{eqnarray*}$ , dann gilt gemäß $\begin{eqnarray*} (a_n) \end{eqnarray*}$ die Gleichung $\begin{eqnarray*} g(T) = \sum_{S\subset T} f(S) = f(T) + \sum_{S\subsetneq T} f(S) \end{eqnarray*}$ , umgestellt $\begin{eqnarray*} f(T) = g(T) - \sum_{S\subsetneq T} f(S) \end{eqnarray*}$ . Für die Mengen $\begin{eqnarray*} S \end{eqnarray*}$ in der Summe rechts ist $\begin{eqnarray*} |S|<n \end{eqnarray*}$ , da sie ja echte Teilmengen von $\begin{eqnarray*} T \end{eqnarray*}$ sind. Folglich ist auf diese $\begin{eqnarray*} S \end{eqnarray*}$ die Induktionsvoraussetzung anwendbar und wir dürfen einsetzen

$\begin{eqnarray*} f(T) = g(T) - \sum_{S\subsetneq T} \sum_{U\subset S} (-1)^{\left|S\setminus U\right|} g(U) \end{eqnarray*}$

Der Rest ist Summation vertauschen und geeignet zusammenfassen bzw. vereinfachen, wobei obige Nebenrechnung einfließt.

2. $\begin{eqnarray*} (b_n)\Rightarrow (a_n) \end{eqnarray*}$ : Läuft nahezu analog ab.

Neue Frage »

Antworten »

Umkehrformel

Verwandte Themen