Beweis von n über k durch vollstaendige Induktion.

Neue Frage »

Ratloser Student Auf diesen Beitrag antworten »
Beweis von n über k durch vollstaendige Induktion.
Meine Frage:
Hi,
die Aufgabe lautet wie folgt:
Es gibt (n ueber k) möglichkeiten, eine k-elementige Menge aus einer n-elementigen Menge auszuwaehlen. K=1,....,n und n element der natuerlichen Zahlen.
Beweisen Sie durch vollstaendige Induktion.

Meine Ideen:
Ich habe das Prinzip der vollstaendigen Induktion verstanden. Doch leider fehlt mir ein Ansatz. Wie sieht der Induktionsanfang ubd der Induktionsschluss aus?
Gast11022013 Auf diesen Beitrag antworten »
RE: Beweis von n über k durch vollstaendige Induktion.
Naja, die Aussage ist folgende:

Die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge ist gleich .


Der Induktionsanfang mit n=1 ist wie?

[Was für Teilmengen hat eine 1-elementige Menge denn?]
ratloser student Auf diesen Beitrag antworten »

Das Ergebnis wäre 1, wenn ich für n=1 einsetze, denn 1!/0! wäre gleich 1. Ist das richtig?
Gast11022013 Auf diesen Beitrag antworten »

Ja, schon.

Aber die Begründung, warum dann die Aussage stimmt, fehlt ein bisschen!


Du hast ja dann die Menge und diese hat eine nullelementige Teilmenge (nämlich die leere Menge) und genau eine einelementige Teilmenge, nämlich sich selbst.

Und andererseits ist eben , also stimmt die Aussage.


[Man kann übrigens auch mit n=0 beginnen.]
ratloser Student Auf diesen Beitrag antworten »

Hey,

ja soweit so gut. Ich könnte es jetzt etwas weiter ausführen.

Mit dem Induktionsanfang würde ich es für die kleine Zahl testen. n über k ist 1!/k!(1-k!)=1!/0! = 1. Soweit wäre die Aussage bewiesen für n=1. Doch wie gehts nun weiter. Mein Ansatz wäre nun:

n+1 über k+1. Aber wenn ich das ausmultipliziere, dann komme ich auf keine Lösung. Wer schafft es mir zu helfen?
Gast11022013 Auf diesen Beitrag antworten »

Erstmal solltest Du sauber die Induktionsvoraussetzung formulieren, nämlich:

Die Behauptung sei für Teilmengen der n-elementigen Menge



bewiesen.


Betrachte nun die k-elementigen Teilmengen von

.

Für ist die Behauptung klar.


Man kann also annehmen.


Nun kann man jede k-elementige Teilmenge von genau einer der folgenden Klassen zuordnen:

bestehe aus allen k-elementigen Teilmengen von , die nicht enthalten und aus denjenigen, die enthalten.


Nun kannst Du Dir überlegen, was die Anzahl der Elemente in bzw. in ist.

Da kommt dann die Induktionsvoraussetzung ins Spiel.
 
 
ratloser Student Auf diesen Beitrag antworten »

Induktionsanfang n=1
(1 ü 0) = 1 = 1!/(0! 1!)
(1 ü 1) = 1 = 1!/(1! 0!)

Ind.-Schluss n ->n+1

zu zeigen: Für 0&#8804;k<n gilt (n+1 ü k+1) = (n+1)! / ( (k+1)!(n+1-(k+1))! )
(die anderen Fälle sind schon erledigt, s.o.)
(n+1 ü k+1) = (n ü k) + (n ü k+1) _______(hier wird k<n gebraucht)
= n! / ( k!(n-k)! ) + n! / ( (k+1)!(n-(k+1))! )
= n! / ( k!(n-k)! ) + n! / ( (k+1)!(n-(k+1))! ) ________ersten Bruch mit k+1 erweitern
= (k+1)*n! / ( (k+1)*k!(n-k)! ) + n! / ( (k+1)!(n-k-1)! ) __zweiten Bruch mit n-k erweitern (hier wird wieder k<n gebraucht)
= (k+1)*n! / ( (k+1)!(n-k)! ) + (n-k)*n! / ( (k+1)!(n-k)! )
= [(k+1)*n! + (n-k)*n!] / ( (k+1)!(n-k)! )
= [k+1 + n-k]*n! / ( (k+1)!(n-k)! )
= [n+1]*n! / ( (k+1)!(n-k)! ) ________n-k=n+1-(k+1) verwenden
= (n+1)! / ( (k+1)!(n+1-(k+1))! )

qed
Gast11022013 Auf diesen Beitrag antworten »

Sorry, aber so steige ich da nicht durch.

Bitte benutze doch den Formeleditor!!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »