n tief k ist die Anzahl aller k-elementigen Mengen einer n-elementigen Menge.
rechts vom GLEICH
steht (n-1 tief k) + (n-2 tief k-2) + (n-3 tief k-2) + … + (n-1-k tief 0). BEACHTE hier k<n.
Seien die n Elemente von 1 bis n nummeriert.
1,2,3,4,5,6,7,,8,…, n-3,n-2,n-1,n
nun kann eine k-elementige Teilmengen
1. aus den ersten n-1 Elementen zusammengesetzt sein.
Das geht auf (n-1 tief k) Arten.
oder sie enthält das Element Nr. n.
Also kann man folgende Fälle addieren (Zusammenhängende Ketten von rechts wachsen lassen bis das maximal zusammenhängende rechts in der Elementanordnung noch gewählt wurde)
2. (Falls k > 0) Alle Mengen, die das Element Nr. n enthalten (eine Mögl.) und Nr. n-1 nicht enthalten:
(n-2 tief k-1) Mögl. :die Zahl der k-1 elementigen Teilemengen der ersten n-2 Elemente
Also: (n-2 tief k-1)*1 =(n-2 tief k-1)
3. (Falls k auch >1) Alle Mengen, die die Element Nr. n und n-1 enthalten (eine Mögl.) und Nr. n-2 nicht enthalten:
(n-3 tief k-2) Mögl. :die Zahl der k-2 elementigen Teilmengen der ersten n-3 Elemente
Also: (n-3 tief k-2)*1= (n-3 tief k-2)
4. (Falls k auch >2) Alle Mengen, die die Element Nr. n, n-1, n-2 enthalten (eine Mögl) und Nr. n-3 nicht enthalten:
(n-4 tief k-3) Mögl. :die Zahl der k-2 elementigen Teilmengen der ersten n-3 Elemente
Also: (n-4 tief k-3)*1 =(n-4 tief k-3)
…
?. Die Menge, die die Element Nr. n und n-1, n-2 bis n-k+1 enthält, Nr n-k nicht enthält und auch kein vorheriges Element enthält:
(n-k-1 tief 0) Mögl. :die Zahl der k-2 elementigen Teilemengen der ersten n-3 Elemente
Also: (n-k-1 tief 0)*1 =(n-k-1 tief 0)
Nun das Ganze noch schön zusammenfassen mit Summenzeichen etc. qed. c)
Ich hoffe jetzt mal, du findest für d) und e) eine eigene Erklärung.
Beachte bei d, dass k>0. Du dürftest deshalb bei der Summierung mit einem ausgezeichneten Element starten, das zur Teilmenge gehört.