Vollständige Induktion

Neue Frage »

17.06.2011, 18:42	Kaputtnix	Auf diesen Beitrag antworten »
Vollständige Induktion Meine Frage: Hallo! Ich soll mittels vollständiger Induktion zeigen, dass jede n-elementige Menge genau $\begin{eqnarray} \begin{pmatrix} n \\ k \\ \end{pmatrix} \end{eqnarray}$ Teilmengen mit k Elementen besitzt $\begin{eqnarray} 0 \leq k\leq n \end{eqnarray}$ . Meine Ideen: Also den Induktionsanfang mach ich mit n = 0: $\begin{eqnarray} \begin{pmatrix} 0 \\ 0 \end{pmatrix} \end{eqnarray}$ = 1 Quasi eine Menge mit 0 Elementen hat nur die leere Menge als Element also stimmt das Ergebnis. Ich komm jetzt aber nicht weiter. Klar ist, dass ich $\begin{eqnarray} n\rightarrow n+1 \end{eqnarray}$ laufen lasse. Aber wie weiter?
17.06.2011, 19:04	Ibn Batuta	Auf diesen Beitrag antworten »
Du könntest ja so ansetzen. Betrachte eine $\begin{eqnarray} (n+1) \end{eqnarray}$ -elementige Menge und $\begin{eqnarray} 0\le k\le n+1 \end{eqnarray}$ . Was ist mit den Fällen, wo $\begin{eqnarray} k=0 \end{eqnarray}$ und $\begin{eqnarray} k=n+1 \end{eqnarray}$ ist? Danach würde mir folgendes einfallen. Schau, nachdem du die Fälle oben abgedeckt hast, die Menge $\begin{eqnarray} T \end{eqnarray}$ der $\begin{eqnarray} k \end{eqnarray}$ -elementige Teilmengen von der obigen Menge an und zerlege die in zwei disjunkte Teilmengen, meinetwegen $\begin{eqnarray} T_1 \end{eqnarray}$ und $\begin{eqnarray} T_2 \end{eqnarray}$ , so dass gilt $\begin{eqnarray} \|T\|=\|T_1\|+\|T_2 \end{eqnarray}$ \|. Weil $\begin{eqnarray} n+1>0 \end{eqnarray}$ ist, ist auch die obige Menge nicht leer, also existiert in Element $\begin{eqnarray} e \end{eqnarray}$ in der Menge. Dann gibt es eine Menge, die kein $\begin{eqnarray} e \end{eqnarray}$ beinhaltet und $\begin{eqnarray} n \end{eqnarray}$ Elemente hat. Rauslaufen tut das ganze wohl auf das Additionsgesetz für Binominalkoeffizienten... Ibn Batuta
17.06.2011, 19:21	Kaputtnix	Auf diesen Beitrag antworten »
Für die Fälle k=0 und k=n+1 würde folgen, dass der Binominialkoeffizient 1 ist. Ich verliere jetzt ein bisschen den Blick für das Ziel. . . Wahrscheinlich hab ich den Sinn hinter Frage noch nicht richtig durchschaut. Ich soll zeigen, dass wenn ich meine Menge aufteilen will und jede Teilmenge k Elemente enthalten soll, komme ich auf $\begin{eqnarray} \begin{pmatrix} n \\k \end{pmatrix} \end{eqnarray}$ Teilmengen. Habe ich den Sinn soweit richtig Vertanden? Und was besagt das Additionsgesetz für Binomialkoeffizienten?
17.06.2011, 19:35	lgrizu	Auf diesen Beitrag antworten »
Ich würde Induktion nach k wählen. Da das etwas knifflig ist gebe ich dir einmal die Idee vor. Wir haben $\begin{eqnarray} \begin{pmatrix}n\\1\end{pmatrix}=n \end{eqnarray}$ einelemnetige Teilmengen einer n-Elemnetigen Menge, weiterhin haben wir unsere Induktionsvorraussetzung, wenn wir jetzt jede der $\begin{eqnarray} \begin{pmatrix}n\\k\end{pmatrix} \end{eqnarray}$ k-Elemntigen Teilmengen mit jeder einelemntigen Teilmenge vereinigen haben wir die k+1 elementigen Teilmengen, nun noch zählen, wie viele das sind. Edit: aber aufpassen, es werden einige doppelt gezählt und einige sind nicht k+1-elementig. Ich mache dir das einmal an einem Beispiel einer dreielementigen Menge vor, diese hat die Teilmengen $\begin{eqnarray} \left\{a\right\},\left\{b\right\}, \left\{c\right\} \left\{ab\right\}, \left\{ac\right\}, \left\{bc\right\}, \left\{abc\right\}, \emptyset \end{eqnarray}$ Wir betrachten nunn die zweielementigen Teilmengen: $\begin{eqnarray} \left\{ab\right\} \cup \left\{a\right\} =\left\{ab\right\} \end{eqnarray}$ $\begin{eqnarray} \left\{ab\right\} \cup \left\{b\right\}=\left\{ab\right\} \end{eqnarray}$ $\begin{eqnarray} \left\{ab\right\} \cup \left\{c\right\}=\left\{abc\right\} \end{eqnarray}$ $\begin{eqnarray} \left\{bc\right\} \cup \left\{a\right\}=\left\{abc\right\} \end{eqnarray}$ $\begin{eqnarray} \left\{bc\right\} \cup \left\{b\right\}=\left\{bc\right\} \end{eqnarray}$ $\begin{eqnarray} \left\{bc\right\} \cup \left\{c\right\}=\left\{abc\right\} \end{eqnarray}$ $\begin{eqnarray} \left\{ac\right\} \cup \left\{a\right\}=\left\{ac\right\} \end{eqnarray}$ $\begin{eqnarray} \left\{ac\right\} \cup \left\{b\right\}=\left\{abc\right\} \end{eqnarray}$ $\begin{eqnarray} \left\{ac\right\} \cup \left\{c\right\}=\left\{ac\right\} \end{eqnarray}$ Wir sehen also, es wird eine mehrfach gezählt und andere sind nicht 3-elementig, diese müssen wir wieder abziehen.
17.06.2011, 19:59	Kaputtnix	Auf diesen Beitrag antworten »
Danke erst mal für deine Hilfe Igrizu. Nur nochmal zu dem was ich oben geschrieben hatte . . . war das soweit richtig (nur fürs Verständnis). Warum müssen wir aber jetzt die Menge der k elementigen Teilmengen bin jeder einelementigen Teilmenge vereinigen? Das ist mir noch unklar wozu dieser abstrakte Schritt notwendig ist.
17.06.2011, 20:10	lgrizu	Auf diesen Beitrag antworten »
Wie erhalten wir denn eine k+1-elementige Teilmenge mit Elementen aus einer n-elementigen Menge? In dem wir eine k-elementige nehemen und sie mit einer einelementigen vereinigen (wir nehmen natürlcih ein Element, das nicht bereits in der Teilmenge liegt). Es ist richtig, für k=0 ist $\begin{eqnarray} \begin{pmatrix}n\\0\end{pmatrix}=1 \end{eqnarray}$ , warum du in dem letzten Post k=n+1 bildest ist mir nicht klar, der Induktionsschritt ist doch k-->k+1, das n können wir fest wählen, wir bleiben bei der n-Elementigen Menge und zeigen, dass sie $\begin{eqnarray} \begin{pmatrix}n\\k+1\end{pmatrix} \end{eqnarray}$ k+1-elementige Teilmengen hat. Nun zählen wir. Wir betarchten einmal eine der k-Elementigen Teilmengen, wie viele Elemente hat n, die nicht in der k-elementigen Teilmenge liegen?
Anzeige

17.06.2011, 20:28	Kaputtnix	Auf diesen Beitrag antworten »
Das k=n+1 bezog sich auf den post von Ibn Batuta. Zu deiner Frage: n sollte dann n-k Elemente enthalten. Es tut mir leid aber ich sehe noch immer nicht das Ziel.
17.06.2011, 20:36	lgrizu	Auf diesen Beitrag antworten »
Okay, also noch einmal von vorne, der Induktionsanfang sollte klar sein. Nun haben wir nach Vorraussetzung $\begin{eqnarray} \begin{pmatrix}n \\k \end{pmatrix} \end{eqnarray}$ k-elementige Teilmengen von n. Wir nehmen uns nun eine k-elementige Teilmenge heraus und vereinigen sie mit den Elementen aus n, die nicht in k liegen, wie viele sind das? Das hast du richtig gesagt, es sind n-k. Nun haben wir also $\begin{eqnarray} (n-k) \cdot \begin{pmatrix}n \\k \end{pmatrix} \end{eqnarray}$ k+1 elemetige Teilmengen. Hier sind aber einige mehrfach gezählt, wie viele sind das? Wenn wir die noch abziehen erhalten wir das gewünschte und unsere Induktion ist fertig.
17.06.2011, 20:56	Kaputtnix	Auf diesen Beitrag antworten »
Ich komm nicht dahinter. Soweit ist alles klar, aber ich steige nicht hinter den letzten Schritt. Ich muss mir das eventuell nochmal in ruhe anschauen. Aber danke für deine Hilfe. Ich hoffe ich blick bis morgen noch durch!
17.06.2011, 20:58	lgrizu	Auf diesen Beitrag antworten »
Wir sind doch nun fast am Ende, welchen Schritt genau verstehst du denn nicht?
17.06.2011, 21:15	Kaputtnix	Auf diesen Beitrag antworten »
naja muss ich jetzt die formel $\begin{eqnarray} (n-k)\cdot \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray}$ soweit umformen, das ich auf $\begin{eqnarray} \begin{pmatrix} n \\ k+1 \end{pmatrix} \end{eqnarray}$ komme, was ja dann der Induktionsschritt wäre? was mir noch unklar ist, ist wenn wir unsere $\begin{eqnarray} \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray}$ k-elementigen Teilmengen haben, warum und wie kann ich sie dann wieder zu n hinzunehmen, wenn doch unser n ja aufgeteilt ist?
17.06.2011, 21:18	lgrizu	Auf diesen Beitrag antworten »
Das stimmt nicht ganz. Mit $\begin{eqnarray} (n-k)\cdot \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray}$ werden die k+1 elementige Teilmengen mehrfach gezählt, die Frage ist, wie oft sie gezählt werden.
17.06.2011, 21:23	Kaputtnix	Auf diesen Beitrag antworten »
Gut und wie finde ich das jetzt heraus, also die Anzahl der doppelt gezählten? Ich versuch mir das die ganze Zeit an deinem Beispiel zu erklären und nachzuvollziehen, aber mich verwirrt, dass du die zweielementigen Teilmengen ansehen willst und am Ende feststellst, dass nur eine mehrfachgezählt wird und dich noch stört, dass manche nicht dreielementig sind.
17.06.2011, 21:26	lgrizu	Auf diesen Beitrag antworten »
Die, die nicht dreielementig sind (in meinem Beispiel oben) haben wir ausgeschlossen, denn in n liegen ja n-k Elemente, die nicht in k liegen. Die k+1-elementigen Teilmengen kommen nun k+2 mal vor, einmal benötigen wir sie aber nur, also k+2-1=k+1 und wir erhalten insgesamt $\begin{eqnarray} \frac{n-k}{k+1} \cdot \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray}$ unterschiedliche k+1-elementige Teilmengen von n durch zählen.
17.06.2011, 21:34	Kaputtnix	Auf diesen Beitrag antworten »
okay gut! ich danke dir für deine Hilfe! ich denke wenn ich mir das nochmal an einem Beispiel erläutere dann sollte ich das Prinzip verstanden haben. War echt eine schwere Geburt. Muss noch so einiges lernen. Aber Danke nochmal und schönes Wochenende!
17.06.2011, 21:35	lgrizu	Auf diesen Beitrag antworten »
Du kannst zur Übung die komplette Induktion auch noch mal hier herein schreiben.

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen