Vollständige Induktion

13.11.2013, 15:07

Tensa

Vollständige Induktion

Hallo alle zusammen.

Die zu Lösende Aufgabe lautet:
Zeigen Sie durch vollständige Induktion, dass jede n-elementige Menge genau $\begin{eqnarray*} 2^{n} \end{eqnarray*}$ verschiedene Teilmengen (einschließlich der leeren Menge 0) besitzt.

Mein Hauptproblem, liegt wohl darin das ich nicht wirklich verstehe was von mir verlangt wird. Trozdem habe ich mal einen Versuch gestartet.

Induktionsanfang:
Ich nehme an, das ich zuerst beweisen soll wie man mit $\begin{eqnarray*} 2^{n} \end{eqnarray*}$ auf 0 kommt.

$\begin{eqnarray*} A(n)= 2^{n} - 1 \end{eqnarray*}$ bzw. $\begin{eqnarray*} A(n)= 2^{n} * n \end{eqnarray*}$

n=0

$\begin{eqnarray*} A(0)= 2^{0} - 1 = 0 \end{eqnarray*}$ bzw. $\begin{eqnarray*} A(0)= 2^{0} * 0 = 0 \end{eqnarray*}$

Induktionsschluss:
Hier habe ich angenommen, das der Schluss mit n+1 gemacht wird.

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

Bsp. mit n=0 und n=1

$\begin{eqnarray*} A(0+1)= 2^{0+1} = 2 \end{eqnarray*}$

$\begin{eqnarray*} A(1+1)= 2^{1+1} = 4 \end{eqnarray*}$

Ich habe keine Ahnung, ob die Aufgabe von mir verlangt zweier Potenzen zu Beweisen
aber wenn das der Fall ist, müsste es ja so stimmen.

Ich bedanke mich schon mal im Voraus.

13.11.2013, 15:13

jimmyt

Auf diesen Beitrag antworten »

RE: Aufgabe zur vollständigen Induktion

Zitat:

Original von Tensa
...
Mein Hauptproblem, liegt wohl darin das ich nicht wirklich verstehe was von mir verlangt wird. Trozdem habe ich mal einen Versuch gestartet.
...

Hi,

Vorschlag:
Gehe folgendermaßen vor:

(I.A.) Induktionanfang mit n=0: ...

(I.V.) Induktionannahme: ...

(I.B.) Induktionbehauptung: ...

(I.S.) Induktionschritt n->n+1: ...

Deine Aufgabe ist zu zeigen, daß für alle $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$ gilt: $\begin{eqnarray*} |P(M)| ~=~ 2^n \quad \text{mit} ~ |M| ~=~ n \end{eqnarray*}$ .
$\begin{eqnarray*} P(M) \end{eqnarray*}$ ist die Potenzmenge von $\begin{eqnarray*} M \end{eqnarray*}$ .

Tipp:
$\begin{eqnarray*} 2^0 ~=~ 2^{n-n} ~=~ 2^n \cdot 2^{-n} ~=~ \frac{2^n}{2^n} ~=~ \frac{1}{1} ~=~ 1 ~\neq~ 0 \end{eqnarray*}$

13.11.2013, 15:19

klarsoweit

Auf diesen Beitrag antworten »

RE: Aufgabe zur vollständigen Induktion

Zitat:

Original von Tensa
Induktionsanfang:
Ich nehme an, das ich zuerst beweisen soll wie man mit 2^{n} auf 0 kommt.

A(n)= 2^{n} - 1 bzw. A(n)= 2^{n} * n

n=0

A(0)= 2^{0} - 1 bzw. A(0)= 2^{0} * 0
= 0 = 0

Das ist Unfug, allein schon aus dem Grund, daß nicht definiert ist, was A(n) ist. Außerdem mußt du nicht beweisen, daß man von "2^{n} auf 0 kommt", sondern daß die gemachte Behauptung für n=0 wahr ist. Im übrigen hat eine Menge mit 0 Elementen nicht 0 Teilmengen, sondern genau eine, nämlich die leere Menge.

Zitat:

Original von Tensa
Bsp. mit n=0 und n=1

A(0+1)= 2^{0+1}
= 2

A(1+1)= 2^{1+1}
= 4

Ein Beispiel ist ja ganz nett, aber kein Induktionsschluß. Da mußt du zeigen, daß eine (n+1)-elementige Menge $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ Teilmengen hat, wobei vorausgesetzt werden darf, daß eine n-elementige Menge $\begin{eqnarray*} 2^{n} \end{eqnarray*}$ Teilmengen hat.

13.11.2013, 18:04

Tensa

Auf diesen Beitrag antworten »

Aufgabe zur vollständigen Induktion
Nach langem Probieren, mein zweiter Versuch:

IA: n=0
Annahme: Menge M hat kein Element
Potenzmenge M hat eine Teilmenge, die Leeremenge

|M|=n : Anzahl der elemente in M
|P(M)|= $\begin{eqnarray*} 2^{n} \end{eqnarray*}$ : Anzahl der Teilmengen der Menge M

|P(M)|= $\begin{eqnarray*} 2^{0} = 1 \end{eqnarray*}$ : eine Teilmenge, die Leeremenge

IS: n+1
Annahme: Menge M hat n+1 Elemente
Potenzmenge M hat mehr als eine Teilmenge

|P(M)|= $\begin{eqnarray*} 2^{n+1} = 2^{n} * 2^{n} = 2 * 2^{n} \end{eqnarray*}$ > 1

n=0

|P(M)|= $\begin{eqnarray*} 2^{0+1} = 2 \end{eqnarray*}$ >1

Ich hoffe das ich dem richtigen Ergebnis näher gekommen bin.

13.11.2013, 18:29

klarsoweit

Auf diesen Beitrag antworten »

RE: Aufgabe zur vollständigen Induktion
Was willst du mit n=0 im Induktionsschritt? Und was soll dieses "> 1" verwirrt

Du mußt - und da wiederhole ich mich - zeigen, daß für eine Menge M mit (n+1) Elementen $\begin{eqnarray*} |P(M)|= 2^{n+1} \end{eqnarray*}$ ist. Dabei darfst du verwenden, daß für eine Menge M mit n Elementen $\begin{eqnarray*} |P(M)|= 2^{n} \end{eqnarray*}$ ist.

13.11.2013, 18:32

jimmyt

Auf diesen Beitrag antworten »

RE: Aufgabe zur vollständigen Induktion

Zitat:

Original von Tensa
...
IA: n=0
Annahme: Menge M hat kein Element
Potenzmenge M hat eine Teilmenge, die Leeremenge
|P(M)|= $\begin{eqnarray*} 2^{0} = 1 \end{eqnarray*}$ : eine Teilmenge, die Leeremenge
...

Der Induktionanker ist schon mal gut gelungen. Freude

Nur das Wort Annahme kannst du streichen, weil wir ja nicht annehmen, sondern tatsächlich die elementlose Menge betrachten.

Zitat:

Original von Tensa
...
I.V.:
|M|=n : Anzahl der elemente in M
|P(M)|= $\begin{eqnarray*} 2^{n} \end{eqnarray*}$ : Anzahl der Teilmengen der Menge M
...

Auch gut gelungen, nur würde ich explizit dazu schreiben, daß das deine Induktionvoraussetzung ist. Freude

Zitat:

Original von Tensa
IS: n+1
Annahme: Menge M hat n+1 Elemente
Potenzmenge M hat mehr als eine Teilmenge

|P(M)|= $\begin{eqnarray*} 2^{n+1} = 2^{n} \textcolor{red}{*} 2^{n} = 2 * 2^{n} \end{eqnarray*}$ > 1

n=0

|P(M)|= $\begin{eqnarray*} \textcolor{red}{2^{0+1} = 2} \end{eqnarray*}$ >1

Ich hoffe das ich dem richtigen Ergebnis näher gekommen bin.

Der Induktionschritt ist nicht so gelungen.
Schau dir die rot markierten Sachen nochmal an. Und streiche Annahme, stattdessen Behauptung.
Und das die Potenzmenge mehr als eine Teilmenge hat, ist eh klar, oder etwa nicht? smile

13.11.2013, 18:33

jimmyt

Auf diesen Beitrag antworten »

@klarsoweit :

Du warst 3 min. schneller. smile

13.11.2013, 19:56

Tensa

Auf diesen Beitrag antworten »

Aufgabe zur vollständigen Induktion
Also, auf ein neues.

Für den IS:

Mir ist gerade aufgefallen, das sich |P(M)| verdoppelt, wenn man beim n+1, das n immer um eins vergrößert. $\begin{eqnarray*} |P(M)| = 2^{n+1} = 2^{n} + 2^{n} \end{eqnarray*}$ = 2 * 2^{n}
Das rote müsste ja mein Ergebnis darstellen, den es beweist das sich die Potenzmenge konstant verdoppelt, wenn das n konstant um +1 anwächst.

Ich bedanke mich nochmals, das ihr euch die Zeit für mein Problem nehmt.

13.11.2013, 20:59

jimmyt

Auf diesen Beitrag antworten »

RE: Aufgabe zur vollständigen Induktion

Zitat:

Original von Tensa
...
Ich bedanke mich nochmals, das ihr euch die Zeit für mein Problem nehmt.

Gerne geschehen. smile

Kannst du es auch, wie soll ich sagen, mengentechnisch begründen?

Also wenn bspw. $\begin{eqnarray*} M \end{eqnarray*}$ und $\begin{eqnarray*} \overline{M} \end{eqnarray*}$ zwei endliche Mengen sind mit $\begin{eqnarray*} a\not\in M,~ |M| = n, ~ \overline{M} = M \cup \{a\} \end{eqnarray*}$ :

$\begin{eqnarray*} P(M)=\{\varnothing, e_1,\dots, e_{2^n-1}\} \end{eqnarray*}$

$\begin{eqnarray*} P(\overline{M})=\{\dots\} \end{eqnarray*}$ ???

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen