Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Induktion beweis Menge hat n^2 Teilmengen

Induktion beweis Menge hat n^2 Teilmengen

Schüler Gymnasium, 12. Klassenstufe

Tags: Beweis, Induktion, Menge, Teilmenge

ItsMax aktiv_icon

21:14 Uhr, 24.09.2018

Hallo, es gibt im Internet einige Beispiele, wie diese Aufgabe zu lösen ist, jedoch verstehe ich davon immer nur die Hälfte.

Es geht um folgende Aufgabe: Begründen Sie mit vollständiger Induktion, warum eine Menge aus

n

Elementen genau

2^{n}

Teilmengen besitzt.

Ich kann mir das ganze verbildlichen und verstehe auch, warum die Behauptung richtig ist, jedoch weiß ich nicht, wie ich daraus eine Formel mache, und dann die Induktion anwende.

Die Verankerung schaffe ich noch:

n = 0,

Menge

M =

∅, also hat die Menge

M

genau eine Teilmenge, und zwar die leere Menge.
Nun setzte ich diese 1 (Anzahl der Teilmengen) in folgende Gleichung:

1 = 2^{0},

was stimmt, da alles hoch 0 die Zahl 1 ergibt.

Jetzt kommt der Induktionsschritt, bei welchem ich langsam verzweifle, da ich nichts, was ich dazu finde, verstehe.

n \to (n + 1),

somit ist die Menge

M = {e 1, e 2, e 3, . .

, e (n + 1)}

. Doch wie verfahre ich ab diesem Punkt weiter?

Ich wäre sehr froh, wenn mir jemand den weiteren Schritt ganz simpel erklären könnte.

Vielen Dank!

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

ledum aktiv_icon

21:29 Uhr, 24.09.2018

du bildest alle Teilmengen aus den ersten

n

Elementen, du bekommst, indem du zu jeder das neue Element hinzufuegst doppelt soviel also

2^{n} \cdot 2 = 2^{n + 1}

das ist alles.
Gruss ledum

ItsMax aktiv_icon

21:38 Uhr, 24.09.2018

Leider verstehe ich nicht wirklich, wo dann da der Beweis ist, bzw. was daran die Induktion ist.
Ich kann alle Teilmengen ja so darstellen:

T = {e (1), e (2), e (3), . .

, e (n)}

. Kann ich das dann mit

2^{n}

gleichsetzten?

Respon

21:54 Uhr, 24.09.2018

Versuchen wir es so:
Den Induktionsanfang hast du schon gemacht.
Weiter

z . B

. so:
Sei

M

eine Menge mit

n + 1

Elementen, etwa

M = {a_{1},

. . .

, a_{n + 1}}

. Sei

U

eine Teilmenge von M. Es gibt genau zwei Möglichkeiten:
1. Fall

a_{n + 1} \notin U

.
Dann ist

U

eine Teilmenge von

M' := {a_{1},

. . .

, a_{n}},

und mit der Voraussetzung
gibt es

2^{n}

Teilmengen von

M',

denn

| P (M') | = 2^{n},

also

2^{n}

Teilmengen, die

a_{n + 1}

nicht enthalten.
2. Fall

a_{n + 1} \in U

.
Dann ist

U

von der Form

U = U' \cup {a_{n + 1}},

und

U'

ist eine Teilmenge
von

M' := {a 1,

. . . , an

}

. Nach Voraussetzung gibt es

2^{n}

Möglichkeiten
für

U',

und damit gibt es

2^{n}

Teilmengen von

M,

die

a_{n + 1}

enthalten.
Es gilt also

| P (M) | = | P (M') | + | P (M') | = 2

2^{n} = 2^{n + 1}

ItsMax aktiv_icon

22:59 Uhr, 24.09.2018

Danke für die Erklärung, ich habe das Prinzip nun verstanden.

1440023

1440007

	Status: nicht eingeloggt	Noch nicht registriert?