n-Elementige Menge besitzt 2^n Teilmengen

13.07.2012, 13:19

Gast11022013

n-Elementige Menge besitzt 2^n Teilmengen

Meine Frage:
Hi,

ich möchte beweisen, dass eine n-Elementige Menge $\begin{eqnarray*} 2^n \end{eqnarray*}$ Teilmengen besitzt.

$\begin{eqnarray*} \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\binom{n}{3}+....+\binom{n}{n}=2^n \end{eqnarray*}$

Ich habe mir gedacht, ich mache es über vollständige Induktion.

Meine Ideen:
Induktionsanfang:

$\begin{eqnarray*} n=0 \binom{n}{0}=2^0 1=1 \end{eqnarray*}$

Induktionsschritt:

$\begin{eqnarray*} n \rightarrow n+1 \sum\limits_{k=0}^{n+1} \frac{n!}{k!(n-k)!}=2^{n+1} \end{eqnarray*}$

Ein wenig auseinander gezogen erhalte ich dann:

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} \frac{n!}{k!(n-k)!}=2^{n}+\sum\limits_{k=n}^{n+1} \frac{n!}{k!(n-k)!}=2^{n+1} \end{eqnarray*}$

Dies ist dann:

$\begin{eqnarray*} 2^n+\frac{(n+1)!}{n!(n+1-n)!}=2^{n+1} 2^n+\frac{(n+1)!}{n!}=2^{n+1} \end{eqnarray*}$

Nun kürze ich:

$\begin{eqnarray*} 2^n+(n+1)=2^n\cdot 2 2^n+(n+1)=2^n+2^n n+1=2^n \end{eqnarray*}$

Na ja. Das kann ja nicht stimmen.
Bzw. würde ich aus diesem Ergebnis doch nichts gewinnen. verwirrt

Habe ich mich irgendwo verhauen, oder funktioniert es überhaupt nicht mit Induktion, sondern möglicherweise über den binomischen Lehrsatz?

Danke im Voraus.

Mfg

Edit: Ich hoffe nach mehrfachem editieren ist nun alles korrekt.

13.07.2012, 14:25

riwe

Auf diesen Beitrag antworten »

RE: n-Elementige Menge besitzt 2^n Teilmengen
eine kleine hilfe Augenzwinkern

13.07.2012, 16:27

DP1996

Auf diesen Beitrag antworten »

Wenn es dir nur darum geht:

Zitat:

ich möchte beweisen, dass eine n-Elementige Menge $\begin{eqnarray*} 2^n \end{eqnarray*}$ Teilmengen besitzt.

, dann gestatte ich mir mal, einen wesentlichen einfacheren Beweis anzudeuten:

Man erhält jede Teilmenge einer n-Elementigen Menge, indem man für jedes Element entscheidet, ob es in dieser Teilmenge enthalten ist oder nicht. Man hat also für jedes Element 2 Möglichkeiten (in der Teilmenge oder nicht), der Rest ist klar.

13.07.2012, 16:37

Fragen über Fragen

Auf diesen Beitrag antworten »

Und ich möchte noch schnell sagen, warum du auf eine falsche Aussage stößt: Du summierst Binomialkoeffizienten bis n über n+1 auf, bzw. im n+1ten Summanden taucht ein (-1)! im Nenner auf, was in dem Kontext keinen Sinn macht. Du musst also n durch n+1 ersetzen; dann ergeben die ersten n Summanden aber auch nicht mehr 2^n.

13.07.2012, 17:07

Gast11022013

Auf diesen Beitrag antworten »

Zitat:

Original von DP1996

Man erhält jede Teilmenge einer n-Elementigen Menge, indem man für jedes Element entscheidet, ob es in dieser Teilmenge enthalten ist oder nicht. Man hat also für jedes Element 2 Möglichkeiten (in der Teilmenge oder nicht)

Enthält die Menge dann:

$\begin{eqnarray*} \binom{n}{0}+\binom{n}{1}+...+\binom{n}{n} \end{eqnarray*}$

Teilmengen, wobei

$\begin{eqnarray*} \binom{n}{0} \end{eqnarray*}$

die leere Menge ist und

$\begin{eqnarray*} \binom{n}{n} \end{eqnarray*}$

eine unechte Teilmenge ist.

Brauche ich also nichts weiter zu tuen, als a=b=1 zu setzen und dann über den binomischen Lehrsatz

$\begin{eqnarray*} (a+b)^n=(1+1)^n=2^n \end{eqnarray*}$

zu folgern?

Zitat:

der Rest ist klar.

Ich befürchte nicht ganz. Augenzwinkern

13.07.2012, 17:20

DP1996

Auf diesen Beitrag antworten »

Wenn du die Summe dieser Binomialkoeffizienten nimmst, unterscheidest du die Teilmengen nach der Anzahl ihrer Elemente. Das brauchst du bei meinem Ansatz nicht zu tun, du sagst einfach:

1. Ich kann jede Teilmenge konstruieren, indem ich für jedes Element angebe, ob es in der Teilmenge enthalten ist oder nicht. (Und jede Konstruktion beschreibt eine andere Teilmenge)
2. Wenn ich nun eine Teilmenge konstruieren will, wie viele Möglichkeiten habe ich dann?
Die Antwort auf 2. ist: Für jedes der n Element hat man 2 Möglichkeiten, und die Möglichkeiten für die einzelnen Elemente sind unabhängig voneinander. Folglich hast du $\begin{eqnarray*} 2^n \end{eqnarray*}$ Möglichkeiten, dir eine Teilmenge zu konstruieren, und nach 1. sind die alle verschieden.

Dein Ansatz über die Binomische Formel kann verwendet werden, um die oben erwähnte Identität der Binomialkoeffizienten, nämlich $\begin{eqnarray*} \sum_{k=0}^{n} \binom{n}{k}=2^n \end{eqnarray*}$ , zu beweisen. Deshalb habe ich oben gefragt, ob auch diese Identität gezeigt werden muss.

13.07.2012, 17:23

Gast11022013

Auf diesen Beitrag antworten »

Ich soll bloß beweisen, dass die aufsummierten Binomialkoeffizienten 2^n ergeben.

13.07.2012, 17:31

DP1996

Auf diesen Beitrag antworten »

Dann sags doch Augenzwinkern

Nee, im ernst, du hast damit jetzt drei Möglichkeiten:

1. Du zeigst das über den Binomischen Lehrsatz (wenn du den verwenden darfst)
2. Du argumentierst wie ich, dass eine Menge mit zwei Elementen genau 2^n Teilmengen hat und setzt dann hinzu, dass jede Teilmenge irgendwas zwischen 0 und n Elementen hat.
3. Du bleibst bei deinem ersten Ansatz und bedienst dich vollständiger Induktion (was eigentlich funktionieren müsste)

Neue Frage »

Antworten »

n-Elementige Menge besitzt 2^n Teilmengen

Verwandte Themen