Induktion Binomialkoeffizient

03.11.2011, 19:38

ineedhelp90

Auf diesen Beitrag antworten »

Induktion Binomialkoeffizient

Meine Frage:
Hi Leute, ich habe eine Aufgabe und komme irgendwie nicht weiter. Die Aufgabe lautet:
Sei $\begin{eqnarray*} \begin{pmatrix} n \\ 2 \end{pmatrix} \end{eqnarray*}$ die Anzahl der zweielementigen Teilmengen einer n-elementigen Menge. Zeigen Sie durch Induktion nach n: $\begin{eqnarray*} \begin{pmatrix} n \\ 2 \end{pmatrix} = \frac{n\left(n-1\right) }{2} \end{eqnarray*}$

Hinweis: Betrachten Sie im Induktionsschritt ein beliebiges, aber festes Element und unterscheiden Sie zwei Fälle.

Meine Ideen:
Soweit so gut, nun hab ich mit dem Induktionsanfang n=1 begonnen:
$\begin{eqnarray*} \begin{pmatrix} 1 \\ 2 \end{pmatrix} = \frac{1\left(1-1\right) }{2} = \frac{0}{2} = 0 \end{eqnarray*}$

Doch nun hab ich mir überlegt, ob das so überhaupt richtig ist oder ob ich bereits beim Induktionsanfang von
$\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$ ausgehen muss? Wobei ja erst im Induktionsschritt ein beliebiges, aber festes Element betrachtet werden soll. Deswegen bin ich mir gerade ziemlich unsicher. Des Weiteren soll im Induktionsschritt eine Fallunterscheidung für 2 Fälle getroffen werden, für ein beliebiges Element k. Da hab ich mir überlegt erst $\begin{eqnarray*} k= 0 \end{eqnarray*}$ und danach $\begin{eqnarray*} k\geq n \end{eqnarray*}$ zu betrachten, nun wüsste ich gerne ob diese Vorüberlegung überhaupt richtig ist?

04.11.2011, 09:27

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Ich glaube, du bist da etwas auf dem falschen Dampfer. Du sollst zeigen, daß die Anzahl der zweielementigen Teilmengen einer n-elementigen Menge eben gleich $\begin{eqnarray*} \frac{n(n-1)}{2} \end{eqnarray*}$ ist. Das hat (jedenfalls im Moment) nichts mit $\begin{eqnarray*} \binom n k \end{eqnarray*}$ zu tun.

Als Induktionsanfang würde ich auch n=2 wählen.

04.11.2011, 10:53

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
also wenn n=2, dann folgt der Induktionsanfang:
$\begin{eqnarray*} \begin{pmatrix} 2 \\ 2 \end{pmatrix} = \frac{2\left(2-1\right) }{2} = \frac{2}{2} = 1 = 1 \end{eqnarray*}$

Im Induktionsschritt würde ja nun folgen n -> n+1:
$\begin{eqnarray*} \begin{pmatrix} n+1 \\ 2 \end{pmatrix} = \begin{pmatrix} n \\ 2 \end{pmatrix} + n+ 1 = \frac{n\left(n-1\right) }{2} + n+ 1=\frac{n\left(n-1\right) }{2} + \frac{2\left(n-1\right) }{2} =\frac{n\left(n-1\right)+ 2\left(n-1\right) }{2} = \frac{\left(n-1\right)\left(n+2\right) }{2} \end{eqnarray*}$
aber da hab ja ich nun keine Fallunterscheidung gemacht?

04.11.2011, 11:02

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient

Zitat:

Original von grml90
also wenn n=2, dann folgt der Induktionsanfang:
$\begin{eqnarray*} \begin{pmatrix} 2 \\ 2 \end{pmatrix} = \frac{2\left(2-1\right) }{2} = \frac{2}{2} = 1 = 1 \end{eqnarray*}$

Genau die Gleichheit von $\begin{eqnarray*} \begin{pmatrix} 2 \\ 2 \end{pmatrix} = \frac{2\left(2-1\right) }{2} \end{eqnarray*}$ mußt du begründen.

Zitat:

Original von grml90
Im Induktionsschritt würde ja nun folgen n -> n+1:
$\begin{eqnarray*} \begin{pmatrix} n+1 \\ 2 \end{pmatrix} = \begin{pmatrix} n \\ 2 \end{pmatrix} + n+ 1 \end{eqnarray*}$

Warum sollte dieses gelten?

04.11.2011, 11:09

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient

Zitat:

Original von klarsoweit
Warum sollte dieses gelten?

Ich hätte gedacht, dass wäre dasselbe, nur ausgeklammert?

04.11.2011, 11:13

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Nöö, wieso? $\begin{eqnarray*} \binom n 2 \end{eqnarray*}$ ist die Anzahl der zweielementigen Teilmengen einer n-elementigen Menge. Welche Rechenregeln sich daraus ergeben, steht völlig in den Sternen.

Anzeige

04.11.2011, 11:21

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
wobei, da $\begin{eqnarray*} \begin{pmatrix} n \\ 2 \end{pmatrix} = \begin{pmatrix} n \\ n-2\end{pmatrix} \end{eqnarray*}$

dann müsste $\begin{eqnarray*} \begin{pmatrix} n+1 \\ 2 \end{pmatrix} = \begin{pmatrix} n+1 \\ n-2\end{pmatrix} \end{eqnarray*}$ gelten oder?

04.11.2011, 11:25

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Du verwendest da jetzt Regeln, die (im Moment) überhaupt nicht bewiesen sind.

04.11.2011, 11:30

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
hm aber wie sonst soll ich mit n-> n+1 sonst weiter kommen?

04.11.2011, 11:35

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Nimm mal eine (n+1)-elementige Menge. Da nimmst du jetzt ein Element heraus. Wieviel 2-elementige Teilmengen hat dann die restliche n-elementige Menge?
Wieviel 2-elementige Teilmengen gibt es noch zusätzlich mit dem herausgenommenen Element?

04.11.2011, 11:53

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Na wenn ich ein Element aus einer (n+1)-elementigen Menge heraus nehme, hat sie dann ein Element weniger also n und zusätzlich gibt es nun n+1 2-elementige Teilmengen? Ich glaube ich bin jetzt verwirrt

verwirrt

04.11.2011, 11:55

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient

Zitat:

Original von grml90
und zusätzlich gibt es nun n+1 2-elementige Teilmengen?

Wie kommst du auf n+1 ?

04.11.2011, 12:01

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
ka ich bin jetzt etwas verwirrt, aber ich glaube es müssten dann noch n-1, 2 elementige Teilmengen existieren, da ich ja eine rausgenommen habe? Also wenn ich ein Element aus Der Menge herausnehme, dann nehm ich auch einen Teil der Teilmenge heraus.

04.11.2011, 12:12

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Heidinei. Du hast in der linken Hand n Elemente und in der rechten Hand ein Element. Jetzt brauchen wir die 2-elementigen Mengen, die wir so bilden, daß wir das Element in der rechten Hand mit jeweils einem Element aus der linken Hand kombinieren. Wieviel Teilmengen gibt das?

04.11.2011, 12:21

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Hm es gibt n Teilmengen, da dass Element aus der rechten Hand in jeder Kombination mit einem Element aus der linken Hand enthalten ist?

04.11.2011, 12:23

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Richtig. Wieviel 2-elementige Teilmengen haben wir jetzt also bei einer Menge mit (n+1) Elementen?

04.11.2011, 12:28

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Na ich denke mal (n+1)Teilmengen?

04.11.2011, 12:56

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Ich brech zusammen.
Wir haben die Menge mit n+1 Elementen aufgeteilt in eine n-elementige Menge und in eine Menge mit einem Element.
Wieviel 2-elementige Teilmengen hat jetzt die n-elementige Menge?
Hinzu kommen noch die n Teilmengen, die sich aus dem einen Element in Kombination mit den restlichen n Elementen bilden lassen.
Das gibt zusammen wieviel?

04.11.2011, 13:18

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Ich auch verwirrt

verwirrt

Na die n-elementige Menge hat n Teilmengen + die n Teilmengen (aus Kombination entstanden) =n+n =2n?

04.11.2011, 13:20

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient

Zitat:

Original von grml90
Na die n-elementige Menge hat n Teilmengen

So? Da würde ich doch mal in die Induktionsvoraussetzung schauen.

04.11.2011, 13:28

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Achso sie hat $\begin{eqnarray*} \begin{pmatrix} n \\ 2 \end{pmatrix} \end{eqnarray*}$ 2-elementige Teilmengen + die n Teilmengen (aus Kombination entstanden)?

04.11.2011, 13:38

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Und was kann man laut Induktionsvoraussetzung für $\begin{eqnarray*} \binom n 2 \end{eqnarray*}$ auch noch schreiben?

04.11.2011, 13:42

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Na $\begin{eqnarray*} \frac{n\left(n-1\right) }{2} \end{eqnarray*}$

04.11.2011, 13:47

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Na fein. Und jetzt addiere noch die n 2-elementigen Teilmengen hinzu, die bei einer (n+1)-elementigen Menge hinzukommen.

04.11.2011, 13:50

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Hoffe mal ich hab das jetzt richtig verstanden:

$\begin{eqnarray*} \frac{n\left(n-1\right) }{2} + \begin{pmatrix} n \\ 2 \end{pmatrix} \end{eqnarray*}$

04.11.2011, 13:56

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Nein absolut nicht. Ich bin auch langsam am Ende meines Lateins, wie man das erklären soll.

Bei einer n-elementigen Menge hast du $\begin{eqnarray*} \frac{n(n-1)}{2} \end{eqnarray*}$ 2-elementige Teilmengen.

Bei einer (n+1)-elementigen Menge hast du dasselbe zuzüglich noch weitere n 2-elementige Teilmengen. Was muß man also rechnen?

04.11.2011, 14:00

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Naja, also addiert man dann?
$\begin{eqnarray*} \frac{n\left(n-1\right) }{2} + \frac{n\left(n-1\right) }{2} \end{eqnarray*}$

04.11.2011, 14:12

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Ich geb's auf. Lies, was ich geschrieben habe, mehr kann ich nicht sagen. geschockt

geschockt

04.11.2011, 14:40

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Ich versteh es nur zur Hälfte unglücklich

unglücklich

Ich weiß, dass die n-elementige Menge, folgende n 2-elementige Teilmengen besitzt: $\begin{eqnarray*} \frac{n\left(n-1\right) }{2} \end{eqnarray*}$

Du sagst, dass die (n+1)-elementige Menge dasselbe besitzt zuzüglich weiterer n 2-elementige Teilmengen, d.h.
$\begin{eqnarray*} \frac{n\left(n-1\right) }{2} \end{eqnarray*}$ +zuzüglich weiterer n 2-elementige Teilmengen?

dann könnte man ja schreiben: $\begin{eqnarray*} \frac{n\left(n-1\right) }{2} \end{eqnarray*}$ + $\begin{eqnarray*} \frac{n+1\left((n+1)-1\right) }{2} \end{eqnarray*}$ oder nicht?

04.11.2011, 14:45

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Wenn ich nur wüßte, was in deinem Hirn vorgeht.

Du hast $\begin{eqnarray*} \frac{n\left(n-1\right) }{2} \end{eqnarray*}$ und sollst noch n hinzufügen, was muß man dann schreiben?

04.11.2011, 14:49

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Das wüsste ich selber gerne Big Laugh

Big Laugh

Achso die zuzüglichen n 2-elementigen Teilmengen sind n. Also folgt einfach:

$\begin{eqnarray*} \frac{n\left(n-1\right) }{2} + n \end{eqnarray*}$

04.11.2011, 15:08

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Heureka! smile

smile

Und jetzt fasse das noch zusammen.

04.11.2011, 15:23

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
hehe, ich glaube ich denke ab und zu viel zu kompliziert unglücklich

unglücklich

naja zusammengefasst ergibt das: $\begin{eqnarray*} \frac{n\left(n+1\right) }{2} \end{eqnarray*}$

04.11.2011, 16:19

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Aber bisher hab ich ja noch keine 2 Fälle unterschieden?

04.11.2011, 16:54

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Warum willst du 2 Fälle unterscheiden? verwirrt

verwirrt

Jetzt bist du doch haargenau am Ziel.

04.11.2011, 17:00

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Da ich laut Aufgabenstellung ein beliebiges Element mit Fallunterscheidung betrachten soll:

Hinweis: Betrachten Sie im Induktionsschritt ein beliebiges, aber festes Element und unterscheiden Sie zwei Fälle.

04.11.2011, 17:02

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Hmm. Da bin ich jetzt überfragt. verwirrt

verwirrt

04.11.2011, 17:33

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
ich hätte gedacht, dass ich im induktionsschritt von $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$ ausgehen muss und dann halt $\begin{eqnarray*} k\leq 2 \end{eqnarray*}$ oder $\begin{eqnarray*} k > 2 \end{eqnarray*}$ betrachten soll

04.11.2011, 17:41

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Schlichtes nöö. Was soll denn $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$ sein? Das wurde ja nicht definiert.

04.11.2011, 18:07

grml90

Auf diesen Beitrag antworten »

RE: Induktion Binomialkoeffizient
Ja das stimmt schon. In einem anderen Thread hab ich gelesen:

"Da sollst Du Dir nun ein Element, das Du ziehst anschauen und zwei Fälle unterscheiden und zwar den, daß Du dieses Element aus "der alten" Menge ziehst oder daß das Element das Element ist, das Du hinzugeworfen hast."

12 nächste Seite »

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »