Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Produkt der Elemente einer Teilmenge

Produkt der Elemente einer Teilmenge

Universität / Fachhochschule

Tags: produkt, Teilmenge

Stuudent aktiv_icon

16:12 Uhr, 26.11.2019

Guten Tag!

Für jede Teilmenge

A \subseteq {1, ..., n}

mit

n \in ℕ,

die keien zwei aufeinanderfolgenden Zahlen enthält, sei

p_{A}

das Produkt der Elemente. Weiter sei

p_{\emptyset} := 1

. Zeigen soll ich nun, dass die Summe über alle

{(p_{A})}^{2}

gleich

(n + 1)!

ist.

Anmerken möchte ich, dass wir aktuell beim Thema Induktion sind. Kombinatorische Beweisprinzipien haben wir bislang nur das Schubfachprinzip und das doppelte Abzählen gemacht.

Kann ich das per Induktion zeigen? Wenn meine Teilmenge A dann aber aus nur einem Element bestehen würde hätte ich ein Problem bei

{(p_{A})}^{2} = 1 \neq (1 + 1)! = 2

. Bitte um Hilfe.

Gruß, Niko

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Zu diesem Thema passende Musteraufgaben einblenden

HAL9000

17:35 Uhr, 26.11.2019

Für

n = 1

ist zu rechnen

\sum_{A \subset {1}} {(p_{A})}^{2} = p_{\emptyset}^{2} + p_{{1}}^{2} = 1^{2} + 1^{2} = 2

,

das entspricht dem geforderten

(1 + 1)! = 2! = 2

, daher ist alles in Ordnung mit dem Induktionsanfang

n = 1

.

Tatsächlich hätte ich den Induktionsanfang bei

n = 0

durchgeführt, da ist noch weniger zu rechnen...

Induktionsschritt

n \to n + 1

:

Da würde ich unterscheiden zwischen den Teilmengen

A

, welche das "neue" Element

(n + 1)

enthalten und denen, welche es nicht enthalten...

EDIT: Wie ich gerade beim Nachrechnen feststelle, brauchen wir im Induktionsanfang

n = 0

UND

n = 1

, also beide ....

Stuudent aktiv_icon

15:17 Uhr, 27.11.2019

Danke für die Rückmeldung! Aber warum muss ich die Induktion bei 0 beginnen lassen? Mein

n

ist doch aus

ℕ

und nicht aus

ℕ_{0}

HAL9000

19:13 Uhr, 27.11.2019

Was spricht dagegen, mehr zu machen als gefordert (denn es ist ja

ℕ \subset ℕ_{0}

), wenn dies sogar mit weniger Aufwand verbunden ist?

Da wir den Induktionsanfang eh für zwei aufeinander folgende Werte brauchen, da ziehe ich doch das einfachere n=0,n=1 gegenüber dem dann schon aufwändigeren n=1,n=2 vor.

Ich würde dir raten, dich auf den Induktionsschritt zu konzentrieren, den ich mal als Wink mit dem Zaunpfahl besser

(\leq n) \to n + 1

nenne. ;-)

Stuudent aktiv_icon

20:07 Uhr, 27.11.2019

Ok, danke werde ich machen. :-)

Stuudent aktiv_icon

10:11 Uhr, 28.11.2019

Habe mich mal an die Induktion drangesetzt.

z . z . :

Summe über alle

{(p_{A})}^{2}

ist gleich

(n + 1)!

Beweis per Induktion über

n

.

I.A.:

n = 0

\sum_{A \subseteq {}} {(p_{A})}^{2} = {(p_{\emptyset})}^{2} = 1^{2} = 1 = 1!

Für

n = 1

\sum_{A \subseteq {1}} {(p_{A})}^{2} = {(p_{\emptyset})}^{2} + {(p_{1})}^{2} = 1^{2} + 1^{2} = 2 = (1 + 1) \neq 2!

I.V.: Behauptung gelte für ein beliebiges

n \in ℕ

I.S.:

n \to n + 1

\sum_{A \subseteq {1, ..., n + 1}} {(p_{A})}^{2} = {(p_{\emptyset})}^{2} + {(p_{{1, ..., n + 1}})}^{2} = 1 + \prod_{i = 1}^{n + 1} i

.
Dann müsste ich das Ergebnis noch durch zwei teilen oder? Dürfen ja keine zwei aufeinanderfolgenden Zahlen vorkommen... Dies ist dann für

(n + 1) \in A

Ist das bisher richtig?

HAL9000

18:29 Uhr, 28.11.2019

Nein. Zunächst mal muss ich mich wiederholen (wie so oft wird beim ersten mal nicht richtig zugehört):

> Da würde ich unterscheiden zwischen den Teilmengen

A

, welche das "neue" Element

(n + 1)

enthalten und denen, welche es nicht enthalten...

Dazu führe ich zunächst einige Bezeichnungen ein:

M_{n}

... alle Teilmengen von

{1, \dots, n}

, die keine zwei aufeinander folgenden Zahlen enthalten

M_{n, 1}

... alle Mengen aus

M_{n}

, die

n

enthalten

M_{n, 2}

... alle Mengen aus

M_{n}

, die

n

nicht enthalten

Nun zum Induktionsschritt

(\leq n) \to n + 1

:

Für

A \in M_{n + 1, 1}

haben wir die Struktur auf

A = A' \cup {n + 1}

mit

A' \in M_{n - 1}

, denn

A'

darf auch nicht

n

enthalten, denn sonst wäre ja

n, n + 1 \in A

, was die Voraussetzung verletzt. Andererseits kann man jede Menge

A' \in M_{n - 1}

um das Element

n + 1

ergänzen und hat eine zulässige Menge aus

M_{n + 1, 1}

. Außerdem ist offenkundig

M_{n + 1, 2} = M_{n}

. Damit gilt

\sum_{A \in M_{n + 1}} p_{A}^{2} = \sum_{A \in M_{n + 1, 1}} p_{A}^{2} + \sum_{A \in M_{n, 2}} p_{A}^{2} = \sum_{A' \in M_{n - 1}} p_{A' \cup {n + 1}}^{2} + \sum_{A \in M_{n}} p_{A}^{2}

= \sum_{A' \in M_{n - 1}} p_{A'}^{2} \cdot {(n + 1)}^{2} + \sum_{A \in M_{n}} p_{A}^{2} \overset{I V}{=} {(n + 1)}^{2} \cdot n! + (n + 1)!

= ((n + 1) + 1) \cdot (n + 1)! = (n + 2)!

.

Zu beachten ist, dass hier die Induktionsvoraussetzung (IV) eben nicht nur für

n

, sondern auch für

n - 1

benötigt wurde, daher ist der "doppelte" Induktionsanfang zwingend erforderlich.

Stuudent aktiv_icon

19:42 Uhr, 28.11.2019

Habe den Ablauf nun verstanden und versuche es damit nochmal in eigenständiger Form zu lösen. Vielen Dank für deine Mühe :-)!

1488208

1487932

	Status: nicht eingeloggt	Noch nicht registriert?