vollständige Induktion

26.10.2014, 12:02

Lukases2

vollständige Induktion

Aufgabe: Beweisen Sie mithilfe vollständiger Induktion: Eine n-elementige
Menge $\begin{eqnarray*} M := \left\{ a_1 , a_2 , ... , a_n\right\} \end{eqnarray*}$ hat $\begin{eqnarray*} 2^{n} \end{eqnarray*}$ Teilmengen.

IA: n=1: $\begin{eqnarray*} 2^1 = 2 \end{eqnarray*}$
Aussaege stimmt, denn (leere Menge) und 1 sind 2 Teilmengen von M mit n=1.

IS: n -> n+1:

Beweis:

$\begin{eqnarray*} 2^{n+1}= 2 \cdot 2^n \end{eqnarray*}$
Die Aussage für $\begin{eqnarray*} 2^n \end{eqnarray*}$ sei schon bewiesen. Durch den Faktor 2 verdoppelt sich die Anzahl der Teilmengen, die aber immer noch Teilmenge der neuen Menge M mit n+1 sind. Somit ist bewiesen, dass eine n-elementige Menge $\begin{eqnarray*} 2^n \end{eqnarray*}$ Teilmengen besitzt.

Ist meine Begründung in Ordnung?

26.10.2014, 13:42

RavenOnJ

Auf diesen Beitrag antworten »

RE: vollständige Induktion

Zitat:

Original von Lukases2
Durch den Faktor 2 verdoppelt sich die Anzahl der Teilmengen, die aber immer noch Teilmenge der neuen Menge M mit n+1 sind.

Aber genau das sollst du doch beweisen, nicht einfach nur konstatieren. Nimm die Teilmengen einer n-elementigen Menge plus ein weiteres Element und zeige jetzt, dass es in dieser erweiterten Menge doppelt so viele Teilmengen gibt. Unterscheide dazu die Teilmengen mit und ohne das neue Element.

26.10.2014, 15:30

Lukases2

Auf diesen Beitrag antworten »

Zitat:

Nimm die Teilmengen einer n-elementigen Menge plus ein weiteres Element

$\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$

Zitat:

und zeige jetzt, dass es in dieser erweiterten Menge doppelt so viele Teilmengen gibt.

Jetzt müsste ich doch quasi nur in einem Schritt schreiben:

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

Hier zeigt sich direkt, dass sich die Menge der Teilmengen verdoppelt, wenn n um 1 erhöht wird. Da das immer für den Vorgänger gilt, muss es auch für jeden weiteren Nachfolger gelten, weil der ja wieder Vorgänger seines Nachfolgers ist.

26.10.2014, 15:59

Guppi12

Auf diesen Beitrag antworten »

Ich verstehe diese Argumentation nicht.
Magst du mal erklären, warum die gleiche Argumenation nicht bei $\begin{eqnarray*} 3^n \end{eqnarray*}$ statt $\begin{eqnarray*} 2^n \end{eqnarray*}$ durchgeht, wenn man mal vom Induktionsanfang absieht?

26.10.2014, 16:29

Lukases2

Auf diesen Beitrag antworten »

Zitat:

Magst du mal erklären, warum die gleiche Argumenation nicht bei $\begin{eqnarray*} 3^n \end{eqnarray*}$ statt $\begin{eqnarray*} 2^n \end{eqnarray*}$ durchgeht, wenn man mal vom Induktionsanfang absieht?

Worauf willst du hinaus? Das gilt doch eigentlich dann auch, aber das hat ja nichts mehr mit der Aufgabe zu tun.

Ich weiß jetzt nicht genau, was ich argumentieren soll bzw. worauf ich eigentlich zu arbeite. Fakt ist ja, dass sich die Summe der Teilmengen mit jedem weiteren Element verdoppelt.

$\begin{eqnarray*} M = \left\{ 1 \right\} \end{eqnarray*}$ hat zwei Teilmengen, $\begin{eqnarray*} M = \left\{ 1,2 \right\} \end{eqnarray*}$ hat $\begin{eqnarray*} 2 \cdot 2 \end{eqnarray*}$ Teilmengen, $\begin{eqnarray*} M = \left\{ 1,2,3 \right\} \end{eqnarray*}$ hat $\begin{eqnarray*} 2 \cdot 2 \cdot 2 \end{eqnarray*}$ Teilmengen, usw.. Wie soll ich da jetzt eine entsprechende Begründung formulieren?

26.10.2014, 16:33

Guppi12

Auf diesen Beitrag antworten »

Worauf ich hinaus will, ist folgendes. Wenn sich deine Argumentation (die hier keiner versteht) genau so auch übertragen lässt auf den Fall, dass man zeigen will, dass die Aufgabe so lautet:

Aufgabe: Beweisen Sie mithilfe vollständiger Induktion: Eine n-elementige
Menge $\begin{eqnarray*} M := \left\{ a_1 , a_2 , ... , a_n\right\} \end{eqnarray*}$ hat $\begin{eqnarray*} 3^{n} \end{eqnarray*}$ Teilmengen.

Dann muss die Argumentation falsch sein, denn diese Aussage ist ja falsch. Das hat also zwar wenig mit der Aufgabe zu tun, wohl aber mit der Richtigkeit deiner Argumentation. Auch kann dir die Frage, die ich dir stellte, dabei helfen, herauszufinden, was genau an deiner Argumenation falsch ist. Warum funktioniert sie auch bei $\begin{eqnarray*} 3^n \end{eqnarray*}$ , obwohl sie das eigentlich nicht sollte?

26.10.2014, 16:48

Lukases2

Auf diesen Beitrag antworten »

Meine Argumentation hat anscheinend nichts mehr mir der Aufgabenstellung zu tun, sondern ist einfach nur so dahingestellt. Trotzdem weiß ich nicht, was genau ich falsch mache.

Ist denn der Ansatz $\begin{eqnarray*} 2^{n+1} = 2 \cdot 2^{n} \end{eqnarray*}$ richtig, oder muss ich noch weiter umformen, um irgendwie anders begründen zu können?

26.10.2014, 16:56

Guppi12

Auf diesen Beitrag antworten »

Dieser Induktionsbeweis benötigt eigentlich kaum Umformungen. Er wird fast ausschließlich argumentativ geführt. Wir nehmen an, die Aussage gelte für eine $\begin{eqnarray*} n \end{eqnarray*}$ -elementige Menge $\begin{eqnarray*} \{a_1,...,a_n\} \end{eqnarray*}$ . Jetzt fügen wir zu dieser Menge ein Element hinzu (jetzt haben wir also die Menge $\begin{eqnarray*} \{a_1,...,a_n,a_{n+1}\} \end{eqnarray*}$ ) und überlegen uns, wieviele Teilmengen diese hat.

Wir wissen ja schon aus der Behauptung, dass das tunlichst doppelt so viele Teilmengen sein sollten, wie bei $\begin{eqnarray*} \{a_1,...,a_n\} \end{eqnarray*}$ . Es wäre also gut, wenn wir irgendwie mit einer beliebigen Teilmenge, die wir uns aus $\begin{eqnarray*} \{a_1,...,a_n\} \end{eqnarray*}$ herausnehmen, zwei verschiedene Teilmengen von $\begin{eqnarray*} \{a_1,...,a_n,a_{n+1}\} \end{eqnarray*}$ finden könnten. Fällt dir da was ein?

Neue Frage »

Antworten »

vollständige Induktion

Verwandte Themen