Partialsummen und Zahlenfolgen - Partialsumme arithmetischer Zahlenfolgen p-ter Ordnung

2. Partialsummen und Zahlenfolgen

2.3. Arithmetische Zahlenfolgen p-ter Ordnung

2.3.1. Partialsumme arithmetischer Zahlenfolgen p-ter Ordnung

Für eine allgemeine Summenformel arithmetischer Zahlenfolgen p-ter Ordnung kann der Satz 2.2 verwendet werden.
Satz 2.2.

Ist (a_n) eine arithmetische Zahlenfolge von p-ter Ordnung, so ist die Summenfolge (s_n), s_n = a₁ + a₂ + ... + a_n, eine arithmetische Zahlenfolge von (p + 1)-ter Ordnung und es gilt (6).

s_n =

(

n
1

)

a₁ +

(

n
2

)

b₁¹ +

(

n
3

)

b₁² + ... +

(

n
p+1

)

b₁^p

(6)

Um den Satz 2.2 zu beweisen, sind weitere Definitionen notwendig.
Aus der Bildungsvorschrift der k-ten Differenzfolge von (a_n) durch b_n^k = b_n+1^k-1 - b_n^k-1 folgt b_n+1^k-1 = b_n^k + b_n^k-1.
Außerdem gilt b_n⁰ := a_n.

DEFINITION 2.7.

Die Fakultät n! (gelesen: "n Fakultät") ist das Produkt der ersten n natürlichen Zahlen. Ferner wird 0! = 1 definiert.

DEFINITION 2.8.

Ein Binomialkoeffizient

(gelesen: "n über k ") ist durch die Gleichung (7) definiert.

(

n
k

)

n(n - 1)(n - 2)...(n - (k - 1))

, kÎN (7)

Zusätzlich wird definiert:

(

n
0

)

= 1, nÎN₀

Falls nÎN und k > n ist, so steht im Zähler der Faktor 0, d.h. der gesamte Ausdruck wird 0.
Um den Satz 2.2 zu beweisen, muss zu erst die Gleichung (8) bewiesen werden. Dies kann mit Hilfe der vollständigen Induktion getan werden.

b_n^k =

(8)

Beweis von Gleichung (8).

Behauptung: Die Gleichung (8) gilt für alle k, nÎN.
Induktionsanfang:

	a)	Gleichung (8) gilt für k > p, denn b_n^p+f = 0 (f > 0) und = 0.
	b)	Gleichung (8) gilt für n = 1, denn b₁^k = b₁^k und = b₁^k.

Induktionsvoraussetzung: b_n+1^k-1 = b_n^k + b_n^k-1 für beliebige k, nÎN. Die Gleichung (8) gilt für a) k > t und n = u beliebig oder b) k < t + 1 und n = u.
Induktionsbehauptung:

	a)	Die Gleichung (8) gilt für k = t und n = u.
	b)	Die Gleichung (8) gilt für k = t - 1 und n = u + 1.

Induktionsbeweis:

a)	sei dem Leser als Übung überlassen.
b)	b_u+1^t-1 = b_u^t + b_u^t-1 b_u+1^t-1 = b_u+1^t-1 = b_u+1^t-1 = b₁^t + + b₁^t+u b_u+1^t-1 = b_u+1^t-1 = b_u+1^t-1 =

Wegen der Gültigkeit von Induktionsanfang und Induktionsschritt gilt die Gleichung (8) für alle natürlichen Zahlen n, k.

QED

Eine weitere Begründung der Gleichung (8) wäre es, die Summe als Anzahl der Wege zu interpretieren. So setzt sich a_n zusammen aus b₁^p mal Anzahl aller Wege von b₁^p nach b_n⁰ + b₁^p-1 mal Anzahl aller Wege von b₁^p-1 nach b_n⁰ + ... + b₀⁰ mal Anzahl aller Wege von b₀⁰ nach b_n⁰. Dabei gibt es von b₁^p-r nach b_n⁰ genau (p - r) Wege in Richtung der 0. Reihe und genau (n - (p - r)) Wege in Richtung der n. Spalte, also insgesamt (n - (p - r) + (p - r)) über (p - r) = n über (p - r) verschiedene Wege. Daraus folgt Gleichung (8).
Zur Veranschaulichung dient die schematische Übersicht für p = 3.

1		8		27		64		125		216		...	(0. Reihe)
	7		19		37		61		91		...		(1. Reihe)
		12		18		24		30		36		...	(2. Reihe)
			6		6		6		6		...		(3. Reihe)

Da a_n = b_n⁰ ist, gilt a_n =

a_q =

a_q =�

(9)
Die Gleichung (10) lässt sich mit Hilfe der vollständigen Induktion beweisen.

(10)
Beweis von Gleichung (10).

Behauptung: Die Gleichung (10) gilt für alle nÎN.
Induktionsanfang: Die Gleichung (10) gilt für n = 1, denn

= 1 und

= 1 für q = 0 bzw.

= 0 und

= 0 für q > 0.
Induktionsvoraussetzung: Die Gleichung (10) gilt für n = k.
Induktionsbehauptung: Die Gleichung (10) gilt für n = k + 1.
Induktionsbeweis: