Hans Walser, [20120502]
Gewichtete Summen im Pascal-Dreieck
Es ist:
Die Gewichtung ist rot
markiert.
Wir berechnen den Fall :
Die Abbildung 1
illustriert die Situation im Pascal-Dreieck.
Abb. 1: Situation im
Pascal-Dreieck
Der Beweis lŠuft
induktiv źber s.
Fźr haben wir die
triviale Aussage .
Fźr ergibt sich:
Der letzte Schritt ist
die źbliche Rekursion der Binomialkoeffizienten.
Induktionsannahme: Es
gelte:
Wegen gilt sogar:
Nun transformieren wir
die Variablen t und k wie folgt:
Damit erhalten wir aus :
Wegen kšnnen wir sogar
schreiben:
Nun schreiben wir die
Variablen erneut um, und zwar:
Damit erhalten wir:
Nun addieren wir die
beiden Formeln:
Wir erhalten:
Somit gilt:
Damit ist auch der
Induktionsschritt in Ordnung und die Summenformel bewiesen.
Fźr ergibt sich die
bekannte Rekursionsformel:
Fźr und erhalten wir:
Dies kann in der Form
geschrieben werden.
Die Formel funktioniert
auch fźr negative k, sowie Werte mit , da wir ăau§enŇ Nullen haben.
Fźr den Fall erhalten wir:
Die Abbildung 2
illustriert diesen Sachverhalt.
Abb. 2: Nullen au§erhalb
links
Fźr den Fall erhalten wir:
Die Abbildung 3 illustriert dieses Beispiel.
Abb. 3: Nullen au§erhalb
rechts