Matroids Matheplanet Forum Index
Moderiert von Curufin epsilonkugel
Analysis » Funktionen » Produkt einer Summe ausmultiplizieren
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Produkt einer Summe ausmultiplizieren
MaxIMP2415
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 04.01.2020
Mitteilungen: 62
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-01-24


Ich bin gerade über folgenden Ausdruck gestolpert und weiß nicht ganz, wie ich die Summe zu interpretieren habe:
$$ \prod_{i=1}^{n}(\sum_{k=1}^{n}a_{i_k}b_k)=\sum_{k_1,...,k_n=1}^{n}\prod_{i=1}^{n}(a_{i_{k_i}}b_{k_i}) $$ Soll die Summe eine Verschachteln von Summen darstellen? Aber wie wird das dann evaluiert/wann nimmt das $k_i$ welchen Wert an?

Für den Kontext: Es geht um den Beweis, dass die Determinante des Produkts zweier Matrizen das Produkt der Determinanten der einzelnen Matrizen ist. (Das b hat eigentlich auch noch einen zweiten Index aber den habe ich erstmal weggelassen, da dieser unabhängig ist.)
Wäre sehr dankbar für Ideen.
Falls einer einen anderen Beweis kennt, wäre ich auch für Verlinkung oder Erläuterung sehr dankbar.

LG



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 4577
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-01-24


Es ist ratsam (auch für den Beweis), das allgemeiner zu formulieren:

$\displaystyle \prod_{i=1}^{n} \sum_{k=1}^{m} c(i,k) = \sum_{k_1,\dotsc,k_n=1}^{m} \prod_{i=1}^{n} c(i,k_i).$

Hierbei ist $c : [n] \times [m] \to \IR$ irgendeine Abbildung, wobei $[n] := \{1,\dotsc,n\}$.
 
Ja, du kannst die rechte Seite als geschachtelte Summe

$\displaystyle \sum_{k_1=1}^{m} \dotsc \sum_{k_n=1}^{m} \prod_{i=1}^{n} c(i,k_i)$

schreiben. Du solltest dir das ganze einmal für $n=2$ und $m=3$ explizit hinschreiben und beweisen (Aufgabe!). Der allgemeine Beweis (per Induktion nach $n$ und $m$) ist nicht weiter schwer, wenn man die Definitionen verwendet und das Distributivgesetz nutzt (ansonsten geht hier nichts weiter ein).
 
Es gibt noch eine andere Möglichkeit, die Summe auf der rechten Seite zu definieren, die etwas konzeptioneller ist:
 
Für jede endliche Menge $S$ und jede Abbildung $f : S \to \IR$ ist $\displaystyle\sum_{s \in S} f(s)$ definiert. Man macht das rekursiv. Siehe z. B. hier. Hier hat man die Menge $S = [m]^n$, also die Menge der $n$-Tupel von natürlichen Zahlen zwischen $1$ und $m$, und die Funktion

$\displaystyle f(k_1,\dotsc,k_n) := \prod_{i=1}^{n} c(i,k_i).$



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MaxIMP2415
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 04.01.2020
Mitteilungen: 62
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-01-24


Vielen Dank das werde ich tun!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MaxIMP2415
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 04.01.2020
Mitteilungen: 62
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2020-01-29


Hey, ich habe getan wir Du mit vorgeschlagen hast.
Ist das alles richtig so?:

Beispiel:

Wir wollen den allgemeinen Ausdruck zum Ausmultpilizieren des Produktes von Summen beweisen. Nämlich soll gelten:
$$ \prod_{i=1}^{n}\sum_{k=1}^{m}f(i,k) = \sum_{k_1=1}^{m}\sum_{k_2=1}^{m}...\sum_{k_n=1}^{m}\prod_{i=1}^{n}f(i,k_i)$$ Um ein Gefühl dafür zu kriegen, wieso das stimmt, schreiben wir die Audrücke für n=2 und m=3 aus. Für die linke Seite:
$$ \prod_{i=1}^{2}\sum_{k=1}^{3}f(i,k)=\prod_{i=1}^{2}(f(i,1)+f(i,2)+f(i,3))$$ $$= (f(1,1)+f(1,2)+f(1,3))*(f(2,1)+f(2,2)+f(2,3)) $$ $$= f(1,1)*f(2,1)+f(1,1)*f(2,2)+f(1,1)*f(2,3)$$ $$+ f(1,2)*f(2,1) + f(1,2)*f(2,2) + f(1,2)*f(2,3) $$ $$+ f(1,3)*f(2,1)+ f(1,3)*f(2,2)+f(1,3)*f(2,3) $$ Und für die rechte Seite:
$$ \sum_{k_1=1}^{3}\sum_{k_2=1}^{3}\prod_{i=1}^{2}f(i,k_i)=\sum_{k_1=1}^{3}\sum_{k_2=1}^{3}(f(1,k_1)*f(2,k_2))$$ $$=\sum_{k_1=1}^{3}(f(1,k_1)*f(2,1)+f(1,k_1)*f(2,2)+f(1,k_1)*f(2,3))$$ $$= f(1,1)*f(2,1) + f(1,1)*f(2,2) * f(1,1)*f(2,3)$$ $$+ f(1,2)*f(2,1) + f(1,2)*f(2,2) + f(1,2)*f(2,3)$$ $$+ f(1,3)*f(2,1) + f(1,3)*f(2,2) + f(1,3)* f(2,3)$$ Wir sehen, dass diese exakt dieselben Terme sind.

Beweis:

Wir führen eine Induktion erst nach nach n und dann nach m durch:
$$ IA: \prod_{i=1}^{1}\sum_{k=1}^{1}f(i,k)= \prod_{i=1}^{1}f(i,1)=f(1,1)=\sum_{k_1=1}^{1}f(1,k_1)=\sum_{k_1=1}^{1}\prod_{i=1}^{1}f(i,k_i) \; \surd $$ Induktion nach n:
$$ IV: \prod_{i=1}^{n}\sum_{k=1}^{1}f(i,k)=\sum_{k_1=1}^{1}\sum_{k_2=1}^{1}...\sum_{k_n=1}^{1}\prod_{i=1}^{n}f(i,k_i)$$ $$ IS: \prod_{i=1}^{n+1}\sum_{k=1}^{1}f(i,k)=\sum_{k=1}^{1}f((n+1),k)*\prod_{i=1}^{n}\sum_{k=1}^{1}f(i,k) \stackrel{IV}{=} \sum_{k=1}^{1}f((n+1),k)*\sum_{k_1,..,k_n=1}^{1}\prod_{i=1}^{n}f(i,k_i)$$ $$ = \sum_{k=1}^{1}f((n+1),k)*\sum_{k_1,..,k_n=1}^{1} (f(1,k_1)*f(2,k_2)*...*f(n,k_n)) $$ Der linke Faktor summiert für ein "weiteres" k mit (n+1) auf.
Wir definieren die Zählvariable k in der ersten Summe daher als $k:=k_{n+1}$
$$ = \sum_{k_1,..k_n,k_{n+1}}^{1}\prod_{i=1}^{n+1}f(i,k_i)  $$ Damit ist gezeigt, dass es für alle n gilt (falls m=1 ist). Nun zeigen wir, dass es auch für alle Kombinationen aus n und m gilt.
\\ Induktion nach m (für n $\in \mathbb{N}$ und m=1 haben wir eben gezeigt  - IA):
$$ IV: \prod_{i=1}^{n}\sum_{k=1}^{m}f(i,k)=\sum_{k_1,..k_n=1}^{m}\prod_{i=1}^{n}f(i,k_i) $$ $$ IS: \prod_{i=1}^{n}\sum_{k=1}^{m+1}f(i,k)=\prod_{i=1}^{n}(\sum_{k=1}^{m}f(i,k)+f(i,(m+1))) \stackrel{Distr}{=}\prod_{i=1}^{n}\sum_{k=1}^{m}f(i,k)+\prod_{i=1}^{n}f(i,(m+1))$$ $$\stackrel{IV}{=} \sum_{k_1,..,k_n=1}^{m}\prod_{i=1}^{n}f(i,k_i)+\prod_{i=1}^{n}f(i,(m+1))= $$ $$\sum_{k_1,..,k_n=1}^{m}(f(1,k_1)*f(2,k_2)*...*f(n,k_n))+ f(1,(m+1))*f(2,(m+1))*...*f(n,(m+1))$$ Der linke Sumand bildet das Produkt von f von i=1,..,n und $k_1,..,k_n$ von 1 bis m (in allen möglichen Kombinationen).
Der rechte fügt den (m+1). für jede Zahl von 1 bis n hinzu:
$$=\sum_{k_1,..k_n=1}^{m+1}(f(1,k_1),..f(n,k_n))=\sum_{k_1,..,k_n}^{m+1}\prod_{i=1}^{n}f(i,k_i) $$



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 4577
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-01-29


Zunächst einmal: aus deinen Fragen hier im Forum schließe ich, dass du noch nicht lange studierst (richtig?). Dafür hast du aber schon sehr ausgeprägte Fähigkeiten, Beweise übersichtlich und korrekt mit LaTeX darzustellen. Und man erkennt dabei auch große Sorgfalt. Das möchte ich einmal ausdrücklich loben!

Leider haben sich in dem Beweis Fehler eingeschlichen.

Zunächst ein stilistischer Kritikpunkt: Es ist für $m=1$ nicht sinnvoll, einen Induktionsbeweis nach $n$ zu machen. Du kannst beide Seiten direkt anhand ihrer Definition ausrechnen.

Zudem ist in deinem Beweis dafür am Ende der letzte Schritt nicht ganz klar begründet, also das $=\sum_{k_1,\dotsc,k_{n+1}} \dotsc$. Welche Recheregel wird hier benutzt?

Im Induktionsbeweis nach $m$ dann kommt der fehler, wo du $\stackrel{Distr}{=}$ schreibst. Erinnere dich, was das Distributivgesetz eigentlich aussagt. Du kannst dir außerdem anhand einfacher Beweise überlegen, dass die Gleichung falsch ist. Die übernächste Gleichung ist ebenfalls falsch.

Der Beweis kann auch so leider nicht funktionieren. Du musst - mit festem $m$ - eine Induktion nach $n$ machen (wobei der Induktionsanfang mit $n=1$ und $m$ bel. wieder direkt zu sehen ist, auch ohne Induktion). Da war mein Hinweis "per Induktion nach $n$ und $m$" oben leider nicht wirklich hilfreich.

Fange also so an:

$\displaystyle \prod_{i=1}^{n+1} \sum_{k=1}^{m} f(i,k) = \left(\prod_{i=1}^{n} \sum_{k=1}^{m} f(i,k)\right) \cdot \sum_{k=1}^{m} f(n+1,k) \stackrel{\text{I.V.}}{=} \dotsc$

Verwende das Distributivgesetz in der folgenden (verallgemeinerten) Form:

$\displaystyle r \cdot \left(\sum_{k=1}^{m} a_k\right) = \sum_{k=1}^{m} r \cdot a_k$

$\displaystyle \left(\sum_{k=1}^{m} a_k\right) \cdot r = \sum_{k=1}^{m} a_k \cdot r$



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MaxIMP2415
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 04.01.2020
Mitteilungen: 62
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-01-29


Danke erst mal für Deine Rückmeldung!

Ja ich studiere seit diesem Wintersemester (an der HU Berlin btw) und die Korrektur der Hausaufgaben ist leider sehr wenig hilfreich (kaum Kommentare und von den wenigen Kommentaren ist ein Großteil schlichtweg falsch) ...

Dass die Gleichung, wo ich $\stackrel{Distr}{=}$ geschrieben habe falsch ist, verstehe ich. Auch den stilistischen Kritikpunkt, verstehe ich. Das werde ich nochmal überarbeiten.
Der letzte Schritt hat mir auch Bauchschmerzen bereitet, aber mein Unterbewusstsein hat mich überredet das einzusehen, damit ich zum Ziel komme ...
Der stimmt nicht, da nicht alls Kombinationen, sondern nur eine Kombination hinzuaddiert wird...

2020-01-29 01:06 - Triceratops in Beitrag No. 4 schreibt: Die übernächste Gleichung ist ebenfalls falsch.
Meinst Du diese hier?:
$$ \sum_{k_1,..,k_n=1}^{m}\prod_{i=1}^{n}f(i,k_i)+\prod_{i=1}^{n}f(i,(m+1))= $$ $$\sum_{k_1,..,k_n=1}^{m}(f(1,k_1)*f(2,k_2)*...*f(n,k_n))+ f(1,(m+1))*f(2,(m+1))*...*f(n,(m+1))$$ Wenn ja-  was soll an dieser Gleichung falsch sein?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MaxIMP2415
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 04.01.2020
Mitteilungen: 62
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-01-29


Mir war nicht klar, dass $$(\sum_{k_1=}^{m}f(k_1))*(\sum_{k_2=1}^{m}f(k_2))=\sum_{k_1=1}^{m}\sum_{k_2=1}^{m}f(k_1)f(k_2) $$ ist. Aber so ist die Verschachteln von Summen ja gerade definiert..

Der überarbeitete Beweis:

Wir führen eine Induktion erst nach nach n und dann nach m durch. \\
Induktion nach n (mit $m \in \mathbb{N}$) beliebeig:
$$ IA: n=1: \prod_{i=1}^{1}\sum_{k=1}^{m}f(i,k)=(f(1,1)+f(1,2)+...+f(1,m))=
\sum_{k_1=1}^{m}\prod_{i=1}^{1}f(i,k_i) \; \surd$$
$$ IV: \prod_{i=1}^{n}\sum_{k=1}^{m}f(i,k)=\sum_{k_1=1}^{m}\sum_{k_2=1}^{m}...\sum_{k_n=1}^{m}\prod_{i=1}^{n}f(i,k_i)$$ $$ IS: \prod_{i=1}^{n+1}\sum_{k=1}^{m}f(i,k)=\sum_{k=1}^{m}f(n+1,k)*(\prod_{i=1}^{n}\sum_{k=1}^{m}f(i,k)) \stackrel{IV}{=} \sum_{k=1}^{m}f(n+1,k)*\sum_{k_1,..,k_n=1}^{m}\prod_{i=1}^{n}f(i,k_i)$$ $$ = \sum_{k=1}^{m}f(n+1,k)*\sum_{k_1,..,k_n=1}^{m} (f(1,k_1)*f(2,k_2)*...*f(n,k_n)) $$

$$ \stackrel{Distr.}{=} \sum_{k_1,..k_n}^{m}( \; (\sum_{k=1}^{m}f(n+1,k)) *( f(1,k_1)*f(2,k_2)*...*f(n,k_n)) \; )  $$ $$\stackrel{Disrt.}{=} \sum_{k_1,...,k_n}^{m}(\sum_{k=1}^{m}f(1,k_1)*f(2,k_2)*...*f(n,k_n)* f(n+1,k)) $$ $$ k:= k_{n+1} \Rightarrow \sum_{k_1,..,k_n,k_{n+1}}^{m}\prod_{i=1}^{n+1}f(i,k_i)$$
Damit ist gezeigt, dass es für alle n gilt (mit festem m).
\\ Induktion nach m ($n \in \mathbb{N}$ beliebig):
$$ IA: m=1: \prod_{i=1}^{n}\sum_{k=1}^{1}f(i,k)=\prod_{i=1}^{n}f(i,1) =\sum_{k_1=1}^{1}\sum_{k_2=1}^{1}...\sum_{k_n=1}^{1} \prod_{i=1}^{n}f(i,k_i) \; \surd$$ $$ IV: \prod_{i=1}^{n}\sum_{k=1}^{m}f(i,k)= \sum_{k_1,..k_n=1}^{m}\prod_{i=1}^{n}f(i,k_i) $$ $$ IS: \prod_{i=1}^{n}\sum_{k=1}^{m+1}f(i,k)=(\sum_{k_1=1}^{m+1}f(1,k_1)) *(\sum_{k_2=1}^{m+1}f(2,k_2))*...* (\sum_{k_{n-1}=1}^{m+1}f(n-1,k_{n-1}))* (\sum_{k_n=1}^{m+1}f(n,k_n)) $$ $$ \stackrel{Distr.}{=}\sum_{k_1=1}^{m+1}(f(1,k_1)\sum_{k_2=1}^{m+1}(f(2,k_2)*...*\sum_{k_n=1}^{m+1}f(n,k_n)\stackrel{n-1 Klammern}{)} $$ $$ \stackrel{Distr.}{=} \sum_{k_1=1}^{m+1}...\sum_{k_n=1}^{m+1} (f(1,k_1)*f(2,k_2)*...*f(n,k_n)) = \sum_{k_1,..k_n=1}^{m+1}\prod_{i=1}^{n}f(i,k_i)$$



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 4577
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-01-30


Ich antworte nur auf den ersten Satz, auf den Rest vielleicht morgen oder die Tage.

Die Gleichung

$\displaystyle (1) \quad \sum_{k_1=1}^{m} f(k_1) \, \cdot \, \sum_{k_2=1}^{m} f(k_2) = \sum_{k_1=1}^{m} \sum_{k_2=1}^{m} f(k_1) \cdot f(k_2)$

ist nicht die Definition der geschachtelten Summe. Die geschachtelte Summe für Ausdrücke $b(k_1,k_2)$ mit zwei Variablen ist definiert durch einfaches Klammern und Anwendung der Definition der normalen Summe:

$\displaystyle \sum_{k_1=1}^{m} \sum_{k_2=1}^{m} b(k_1,k_2) := \sum_{k_1=1}^{m} \left ( \sum_{k_2=1}^{m} b(k_1,k_2) \right)$

Die Gleichung $(1)$ folgt nun aus den von mir genannten allgemeinen Distributivgesetzen:

$\displaystyle \begin{align*}
\sum_{k_1=1}^{m} f(k_1) \, \cdot \, \sum_{k_2=1}^{m} f(k_2) & \stackrel{\text{Distr.}}{=} \sum_{k_1=1}^{m} \left(f(k_1) \cdot \sum_{k_2=1}^{m} f(k_2) \right) \\
&\stackrel{\text{Distr.}}{=}  \sum_{k_1=1}^{m} \left(\sum_{k_2=1}^{m} f(k_1) \cdot f(k_2) \right)\\
&\stackrel{\text{Def.}}{=}  \sum_{k_1=1}^{m} \sum_{k_2=1}^{m} f(k_1) \cdot f(k_2)
\end{align*}$



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 4577
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-01-31


Hinweise zu deinem Beweis:

1) In der Induktion nach $n$ ist $m$ beliebig. Danach bist du also fertig. Du musst nicht eine zweite Induktion nach $m$ starten.
2) Im Beweis verwendest du Pünktchen. Versuche, diese beim Beweis solcher grundlegenden Rechenregeln zu vermeiden, weil gewissermaßen geht es hier gerade darum, solche Pünktchenschreibweisen zu präzisieren.
3) Es ist eher unschön, dass du $f(n+1,k)$ als ersten Faktor ausklammerst, weil du dann zwei mal die Kommutativität der Multiplikation anwendest, obwohl sie nicht gebraucht wird. Es ist (so hatte ich es auch im Tipp geschrieben) besser, $f(n+1,k)$ als letzten Faktor auszuklammern.
4) Die Schreibweise $k := k_{n+1} \implies$ ist unglücklich. Eigentlich sollte die Gleichungskette mit $=$ weitergehen.
5) Den zweiten Induktionsbeweis habe ich nur überflogen - er ist wie gesagt auch nicht nötig. Hier scheinst du keinen Beweis zu führen, sondern die Behauptung mit Pünktchen zu belegen. Wie gesagt ist das nicht präzise.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MaxIMP2415 hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]