Vollständige Induktion anhand von (n¦k)=n!/k!(n-k)! ?

3 Antworten

Ich schreibe den Binomialkoeffizienten "n über k" als (n|k)

Wir werden benutzen, dass (n+1|k) = (n|k) + (n|k-1). Interpretation: k Elemente aus n+1 Elementen auswählen ist wie entweder k aus den ersten n auszuwählen oder das (n+1)-te Element und k-1 aus den ersten n auszuwählen.

Induktionsbeginn mit n=1: selber machen..

Induktionsannahme: Wir haben es für n und alle k=0,1,....,n bewiesen.

Induktionsschritt:

(n+1|k) =

(n|k) + (n|k-1) =

(nach Voraussetzung) n! / k! / (n-k)! + n! / (k-1)! / (n-k+1)! =

(n+1)! / k! / (n-k+1)! [ (n-k+1)/(n+1) + k/(n+1) ] =

(n+1)! / k! / (n-k+1)!

Was zu beweisen war.

Mal 'n blöde Frag: Bist du dir sicher, dass die Aufgabe so lautet? Der Binomialkoeffizient ist ja nämlich eigentlich so definiert, wie es da steht. Von daher gibt es da nicht viel zu beweisen.

Man kann höchstens über die Rechenregeln, die für den Binomialkoeffizienten gelten, den Induktionsschluss probieren. Die Rechenregeln basieren allerdings auf der Aussage, die man beweisen will, von daher wäre das auch ein bisschen witzlos.

Unabhängig davon ist im Allgemeinen

n!/k!(n-k)! ungleich (n+1)!/k!((n+1)-k)!

Was willst du denn beweisen? Das (n über k) so definiert ist kann man nicht beweisen, das is einfach die Notation dazu.

Was möchtest Du wissen?