Hans Walser, [20120502]

Gewichtete Summen im Pascal-Dreieck

1        Die Formel

Es ist:

Die Gewichtung ist rot markiert.

2        Beispiel und Illustration

Wir berechnen den Fall :

Die Abbildung 1 illustriert die Situation im Pascal-Dreieck.

Abb. 1: Situation im Pascal-Dreieck

3        Beweis

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.

4        SonderfŠlle

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