Die Fakultät und der Binomialsatz – Analysis I (Kap. 1-9)

3.3 Die Fakultät und der Binomialsatz

3.3.1 Fakultät

Definition 3.24 (Fakultät).

Die Funktion $n \in ℕ_{0} \mapsto n! \in ℕ$ ist definiert durch

\begin{array}{l} 0! = 1, n! = \prod_{k = 1}^{n} k . \end{array}

Die Zahl $n!$ wird als $n$ –Fakultät oder $n$ –Faktorielle bezeichnet.

Insbesondere (nämlich per Definition des Produkts) gilt also die rekursive Formel

\begin{array}{l} (n + 1)! = (n!) \cdot (n + 1) \end{array}

für alle $n \in ℕ_{0}$ . Wir werden dieser Funktion in vielen weiteren Funktionen und Ausdrücken begegnen. Sie hat jedoch auch für sich gesehen eine (kombinatorische) Bedeutung.

Lemma 3.25 (Kardinalität der Menge der Permutationen einer endlichen Menge).

Für $n \in ℕ$ ist $n!$ die Kardinalität der Menge $𝒮_{n}$ der bijektiven Abbildungen $σ : {1, \dots, n} \to {1, \dots, n}$ (auch Permutationen von ${1, \dots, n}$ genannt).

Intuitiv ausgedrückt gibt es also genau $n!$ verschiedene Möglichkeiten die Menge ${1, \dots, n}$ zu sortieren oder auch $n!$ Möglichkeiten für die verschiedenen Reihenfolgen, wenn alle $n$ nummerierte Bälle zufällig aus einer Urne gezogen werden.

Bemerkung.

Zu $n \in ℕ$ bildet die Menge $𝒮_{n}$ zusammen mit der Verknüpfung von Elementen $(σ, τ) \in 𝒮_{n}^{2} \mapsto σ \circ τ \in 𝒮_{n}$ eine Gruppe (die symmetrische Gruppe).

Beweis von Lemma 3.25.

Wir beweisen die Aussage per Induktion. Für $n = 1$ gibt es genau eine (bijektive) Abbildung ${1} \to {1}$ , was den Induktionsanfang darstellt.

Angenommen die Aussage des Lemmas gilt bereits für ein $n \in ℕ$ . Wir betrachten nun eine Permutation $σ$ von ${1, \dots, n + 1}$ . Falls $σ (n + 1) = n + 1$ gilt, so erhalten wir mittels Einschränkung auf ${1, \dots, n}$ eine bijektive Abbildung $σ^{'} : k \in {1, \dots, n} \to {1, \dots, n}$ in $𝒮_{n}$ . Umgekehrt können wir für jedes $σ^{'} \in 𝒮_{n}$ eine Fortsetzung $σ \in 𝒮_{n + 1}$ mit $σ (n + 1) = n + 1$ definieren. Daher wissen wir also per Induktionsannahme, dass es $n!$ Abbildungen $σ \in 𝒮_{n + 1}$ mit $σ (n + 1) = n + 1$ gibt. Wir bezeichnen die Menge aller solcher Permutation in $𝒮_{n + 1}$ mit

H = {σ \in 𝒮_{n + 1} ∣ σ (n + 1) = n + 1},

so dass $| H | = n!$ .

Die Menge $𝒮_{n + 1}$ lässt sich wie folgt partitionieren:

\begin{array}{l} 𝒮_{n + 1} = ⨆_{k = 1}^{n + 1} P_{k} mit P_{k} = {τ \in 𝒮_{n + 1} ∣ τ (n + 1) = k} \end{array}

für $k = 1, \dots, n + 1$ . Wir behaupten nun, dass die Mengen $P_{k}$ auf der rechten Seite alle Kardinalität $n!$ haben (für $k = n + 1$ ist dies bereits bekannt, da $P_{n + 1} = H$ ). Dies impliziert

\begin{array}{l} | 𝒮_{n + 1} | = (n!) \cdot (n + 1) = (n + 1)! \end{array}

und damit nach vollständiger Induktion das Lemma.

$PIC$

Figur 3.1: Wir haben

𝒮_{n + 1}

n + 1

Teile zerlegt und beweisen, dass jedes Element dieser Partition genau

n! = | H |

Elemente enthält. Dazu konstruieren wir für jedes

k \in {0, \dots, n}

eine Bijektion

P_{k} \to P_{n + 1} = H

Sei $k \in {1, \dots, n}$ fix und sei $δ_{k} : {1, \dots, n + 1} \to {1, \dots, n + 1}$ die bijektive Abbildung, die $k$ und $n + 1$ vertauscht und sonst wirkungslos ist, das heisst, die Abbildung

\begin{array}{l} δ_{k} : {1, \dots, n + 1} \to {1, \dots, n + 1}, ℓ \mapsto {\begin{matrix} k & falls ℓ = n + 1 \\ n + 1 & falls ℓ = k \\ ℓ & falls ℓ \notin {k, n + 1} . \end{matrix} \end{array}

Falls nun $τ \in 𝒮_{n + 1}$ die Eigenschaft $τ (n + 1) = k$ hat, dann bildet $σ = δ_{k} \circ τ \in 𝒮_{n + 1}$ das Element $n + 1$ auf $n + 1$ ab. Die Abbildung

\begin{array}{l} Φ : τ \in P_{k} \mapsto δ_{k} \circ τ \in H = {σ \in 𝒮_{n + 1} ∣ σ (n + 1) = n + 1} \end{array}

ist somit wohldefiniert. Sie ist auch bijektiv, da die Abbildung

σ \in H = P_{n + 1} \mapsto δ_{k} \circ σ = τ \in P_{k}

eine Inverse darstellt. Für $σ \in H$ gilt $δ_{k} \circ σ (n + 1) = δ_{k} (n + 1) = k$ und damit definiert $σ \in H \mapsto Ψ (σ) = δ_{k} \circ σ$ eine Abbildung $Ψ : H \to P_{k}$ . Des Weiteren ist die Verknüpfung $δ_{k} \circ δ_{k}$ die Identität auf ${1, \dots, n + 1}$ , womit man $Ψ \circ Φ (τ) = τ$ für $τ \in P_{k}$ und ebenso $Φ \circ Ψ (σ) = σ$ für $σ \in H$ erhält. Dies beweist die obige Behauptung, was den Beweis des Induktionsschritts abschliesst.

■

3.3.2 Binomialkoeffizienten

Für $n, k \in ℕ_{0}$ mit $0 \leq k \leq n$ definieren wir den Binomialkoeffizienten $(\binom{n}{k})$ , als „ $n$ über $k$ “ ausgesprochen, durch

\begin{array}{l} (\binom{n}{k}) = \frac{n!}{k! (n - k)!} . \end{array}

Ersetzen wir $k$ bei gleichbleibendem $n$ im Binomialkoeffizienten durch $n - k$ , so vertauschen sich bloss die beiden Ausdrücke im Nenner und wir erhalten

\begin{array}{l} (\binom{n}{k}) = (\binom{n}{n - k}) \end{array}

für alle $k, n \in ℕ_{0}$ mit $0 \leq k \leq n$ .

Proposition 3.26 (Additionseigenschaft der Binomialkoeffizienten).

Für $n \in ℕ_{0}$ und $k \in ℕ$ mit $1 \leq k \leq n$ gelten $(\binom{n}{0}) = (\binom{n}{n}) = 1$ und die Additionsformel

\begin{align} (\binom{n}{k - 1}) + (\binom{n}{k}) = (\binom{n + 1}{k}) . & (3.3) \end{align}

Insbesondere ist $(\binom{n}{k}) \in ℕ$ für alle $n, k \in ℕ_{0}$ mit $0 \leq k \leq n$ .

$PIC$

Figur 3.2: Die Binomialkoeffizienten lassen sich auch bildlich im sogenannten Pascal Dreieck festhalten, wobei in der

n

-ten Zeile die Zahlen

(\binom{n}{0}), (\binom{n}{1}), (\binom{n}{2}), \dots, (\binom{n}{n})

stehen und die diagonalen Striche die Additionsformel (3.3) in Proposition 3.26 andeuten.

Beweis.

Wir verwenden die Definition der Binomialkoeffizienten und erhalten

\begin{array}{l} (\binom{n}{0}) = (\binom{n}{n}) = \frac{n!}{0! n!} = 1 \end{array}

sowie

\begin{array}{l} (\binom{n}{k - 1}) + (\binom{n}{k}) & = \frac{n!}{(k - 1)! (n - (k - 1))!} + \frac{n!}{k! (n - k)!} \\ = \frac{k n!}{k! (n + 1 - k)!} + \frac{(n + 1 - k) n!}{k! (n + 1 - k)!} \\ = \frac{(k + n + 1 - k) n!}{k! (n + 1 - k)!} = (\binom{n + 1}{k}) \end{array}

durch Erweiterung mit $k$ beziehungsweise $n + 1 - k$ .

Die Aussage, dass $(\binom{n}{k}) \in ℕ$ für alle $k \in ℕ_{0}$ mit $0 \leq k \leq n$ , ergibt sich aus den ersten beiden Aussagen und Induktion nach $n$ . In der Tat entsteht die jeweils nächste Zeile im Pascal Dreieck (siehe Bild 3.2), indem man an den Rändern jeweils eine $1$ und dazwischen die Summen aus der vorherigen Zeile niederschreibt.

■

Wichtige Übung 3.27 (Kombinatorische Bedeutung der Binomialkoeffizienten).

Beweisen Sie, dass die Zahl $(\binom{n}{k})$ für $n, k \in ℕ_{0}$ mit $0 \leq k \leq n$ die möglichen Resultate bei der Auswahl einer $k$ -elementigen Teilmenge von ${1, \dots, n}$ darstellt. Formaler ausgedrückt: Zeigen Sie, dass es genau $(\binom{n}{k})$ Teilmengen von ${1, \dots, n}$ gibt, die $k$ Elemente besitzen. Berechnen Sie $(\binom{42}{6})$ (beziehungsweise $(\binom{49}{6})$ falls Sie aus Deutschland stammen oder $(\binom{45}{6})$ falls Sie aus Österreich stammen).

Hinweis.

Wir stellen uns vor, dass wir die Elemente der Menge ${1, \dots, n}$ in beliebiger Reihenfolge auflisten und wir mit den jeweils ersten $k$ Elemente eine $k$ -elementige Teilmenge $A \subseteq {1, \dots, n}$ definieren wollen. Auf Grund von Lemma 3.25 gibt es insgesamt $n!$ viele Möglichkeiten, die Elemente von ${1, \dots, n}$ aufzulisten. Wenn wir die ersten $k$ Elemente der Liste anders ordnen (mit $k!$ vielen Möglichkeiten) oder auch die letzten $(n - k)$ Elemente der Liste anders ordnen (mit $(n - k)!$ vielen Möglichkeiten), so ändert sich zwar unsere Liste, doch die durch die Liste definierte Teilmenge $A \subseteq {1, \dots, n}$ ändert sich nicht. Dies erklärt, warum es genau $(\binom{n}{k}) = \frac{n!}{k! (n - k)!}$ viele $k$ -elementigen Teilmengen von ${1, \dots, n}$ gibt.

Obige kombinatorische Bedeutung liefert sowohl eine Interpretation als auch einen kombinatorischen Beweis von (3.3): Angenommen wir haben $n + 1$ Bälle mit den Zahlen $1$ bis $n + 1$ beschriftet, doch hat der letzte Ball $n + 1$ die Farbe rot und alle anderen die Farbe blau. Sei nun $1 \leq k \leq n$ . Für jede der $(\binom{n + 1}{k})$ Möglichkeiten $k$ Bälle aus den $n + 1$ Bällen auszuwählen fällt nun zuerst auf, ob der rote Ball ausgewählt wurde oder nicht. In dem ersten Fall haben wir den roten Ball gemeinsam mit einer der $(\binom{n}{k - 1})$ Auswahlmöglickeiten für $k - 1$ Bälle aus den $n$ blauen Bällen. Im zweiten Fall sehen wir eine der $(\binom{n}{k})$ Auswahlmöglichkeiten für $k$ Bälle aus den $n$ blauen Bällen. Dies definiert also eine Bijektion zwischen den $(\binom{n + 1}{k})$ Auswahlmöglichkeiten für $k$ aus $n + 1$ und der (disjunkten) Vereinigung der $(\binom{n}{k - 1})$ Auswahlmöglichkeiten für $k - 1$ aus $n$ und den $(\binom{n}{k})$ Auswahlmöglichkeiten für $k$ aus $n$ , wodurch (3.3) nochmals bewiesen wird.

3.3.3 Der binomische Lehrsatz

Satz 3.28 (Binomischer Lehrsatz).

Für $w, z \in ℂ$ und $n \in ℕ_{0}$ gilt

\begin{array}{l} {(w + z)}^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) w^{n - k} z^{k} . \end{array}

Die Geschichte des binomischen Lehrsatz ist zum einen ziemlich verzweigt und zum anderen ziemlich lang. Die erste Formulierung eines Spezialfalls des binomischen Lehrsatzes wird bereits Euklid zugeschrieben. Der binomische Lehrsatz und die Binomialkoeffizienten waren den Hindus im ersten Jahrtausend vermutlich bekannt, die erste, relativ exakte Formulierung geht wahrscheinlich auf den persischen Mathematiker Al-Karaji zurück, der den Lehrsatz mit einer groben Variante von vollständiger Induktion bewies. Wir verweisen unter anderem auf [Coo49] für mehr Details.

Beweis des binomischen Lehrsatzes.

Wir verwenden vollständige Induktion über $n$ . Für $n = 0$ gilt die Aussage, da

\begin{array}{l} {(w + z)}^{0} = 1 = \sum_{k = 0}^{0} 1 w^{0 - k} z^{k} . \end{array}

Angenommen die Aussage des Satzes gilt für ein $n \in ℕ_{0}$ . Dann erhalten wir

\begin{array}{l} {(w + z)}^{n + 1} & = {(w + z)}^{n} (w + z) = (\sum_{k = 0}^{n} (\binom{n}{k}) w^{n - k} z^{k}) (w + z) \\ = \sum_{k = 0}^{n} (\binom{n}{k}) w^{n + 1 - k} z^{k} + \sum_{k = 0}^{n} (\binom{n}{k}) w^{n - k} z^{k + 1} \\ = w^{n + 1} + \sum_{k = 1}^{n} (\binom{n}{k}) w^{n + 1 - k} z^{k} + \sum_{j = 0}^{n - 1} (\binom{n}{j}) w^{n - j} z^{j + 1} + z^{n + 1} \\ = w^{n + 1} + \sum_{k = 1}^{n} (\binom{n}{k}) w^{n + 1 - k} z^{k} + \sum_{k = 1}^{n} (\binom{n}{k - 1}) w^{n + 1 - k} z^{k} + z^{n + 1} \\ = w^{n + 1} + \sum_{k = 1}^{n} (\binom{n + 1}{k}) w^{n + 1 - k} z^{k} + z^{n + 1} \\ = \sum_{k = 0}^{n + 1} (\binom{n + 1}{k}) w^{n + 1 - k} z^{k} \end{array}

unter Verwendung einer Indexverschiebung und der Additionsformel (3.3).

■

Übung 3.29 (Summe der Binomialkoeffizienten).

Zeigen Sie für jedes $n \in ℕ_{0}$ die Identitäten

\begin{array}{l} \sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}, \sum_{k = 0}^{n} {(- 1)}^{k} (\binom{n}{k}) = {\begin{matrix} 1, & falls n = 0, \\ 0, & falls n \geq 1 . \end{matrix} \end{array}

Hinweis.

Setzen Sie spezielle Werte für die Variablen im binomischen Lehrsatz ein.

Übung 3.30 (Eine weitere Summe).

Verwenden Sie den binomischen Lehrsatz, um die Identität

\begin{array}{l} \sum_{m = k}^{n} (\binom{m}{k}) (\binom{n}{m}) = (\binom{n}{k}) 2^{n - k} \end{array}

für alle $k \leq n$ zu beweisen. Dies verallgemeinert die erste Aussage aus Übung 3.29, wieso? Können Sie einen kombinatorischen Beweis für diese Aussage finden?

Hinweis.

Betrachten Sie das Polynom $p (x) = {(1 + (1 + x))}^{n} = {(2 + x)}^{n}$ und finden Sie den Koeffizienten von $x^{k}$ unter Verwendung des binomischen Lehrsatzes. Für den kombinatorischen Beweis wählen sie aus $n$ Bällen zuerst $j \geq k$ und aus diesen anschliessend $k$ Bälle aus. Auf diese Weise erhalten Sie wiederum $k$ Bälle aus $n$ Bällen, doch ergeben sich hier Vielfachheiten.

Übung 3.31 (Das Multinomialtheorem).

In dieser Übung möchten wir in Analogie zum binomischen Lehrsatz (Satz 3.28) Ausdrücke der Form ${(z_{1} + \dots + z_{d})}^{n}$ für komplexe Zahlen $z_{1}, \dots, z_{d}$ und $n \in ℕ_{0}$ untersuchen. Wir betrachten dazu sogenannte Multiindizes $α \in ℕ_{0}^{d}$ . Ist $α = (α_{1}, \dots, α_{d}) \in ℕ_{0}^{d}$ ein Multiindex, $n = \sum_{k = 1}^{d} α_{k}$ und $z = (z_{1}, \dots, z_{d}) \in ℂ^{d}$ , so definieren wir

\begin{array}{l} (\binom{n}{α}) = \frac{n!}{(α_{1}!) \dots (α_{n}!)} \end{array}

sowie

\begin{array}{l} z α = z_{1}^{α_{1}} \dots z_{d}^{α_{d}} . \end{array}

Zeigen Sie für alle $z = (z_{1}, \dots, z_{d}) \in ℂ^{d}$ und $n \in ℕ_{0}$ das Multinomialgesetz

\begin{array}{l} {(z_{1} + \dots + z_{d})}^{n} = \sum_{α \in ℕ_{0}^{d} : α_{1} + \dots + α_{d} = n} (\binom{n}{α}) z α . \end{array}

Hinweis.

Verwenden Sie Satz 3.28 und Induktion nach $d$ .

3.3.4 Summen von Potenzen

In diesem Teilabschnitt wollen wir mit Hilfe des Binomialsatzes Lemma 1.3 für beliebige Potenzen verallgemeinern.

Proposition 3.32 (Summe von Potenzen).

Für jedes $d \in ℕ_{0}$ gibt es rationale Konstanten $c_{0}, \dots, c_{d} \in ℚ$ , so dass

\begin{array}{l} \sum_{k = 1}^{n} k^{d} = \frac{1}{d + 1} n^{d + 1} + c_{d} n^{d} + \dots + c_{1} n + c_{0} \end{array}

für alle $n \in ℕ$ gilt.

Anders ausgedrückt ist die Summe der $d$ -ten Potenzen $1^{d} + \dots + n^{d}$ gleich den Funktionswerten eines Polynoms mit Grad $d + 1$ und Leitkoeffizient $\frac{1}{d + 1}$ ausgewertet bei $x = n$ . Wir werden dies im Kapitel 4 verwenden, um Flächeninhalte unter Graphen von Polynomen zu berechnen.

Wir bemerken noch, dass wir für jedes feste $d$ , nach dem Auffinden der rationalen Konstanten, wie in Lemma 1.3 Induktion über $n \in ℕ$ anwenden könnte, um weitere Spezialfälle der Proposition zu beweisen. Stattdessen wollen wir in unserem Beweis Induktion über $d$ anwenden.

Beweis.

Wir behaupten, dass es zu jedem Polynom $p (T) \in ℚ [T]$ mit Grad $d \in ℕ_{0}$ und führendem Koeffizienten $c$ ein Polynom $P (T) \in ℚ [T]$ mit Grad $d + 1$ und führendem Koeffizienten $\frac{c}{d + 1}$ gibt, so dass

\begin{array}{l} \sum_{k = 1}^{n} p (k) = P (n) \end{array}

für alle $n \in ℕ$ gilt. Die Aussage der Proposition ergibt sich aus dieser Behauptung als einfacher Spezialfall. Der Vorteil der verallgemeinerten Behauptung ist, dass wir diese etwas eleganter mittels vollständiger Induktion über $d \in ℕ_{0}$ beweisen können.

Falls $d = 0$ ist, so ist $p = c$ konstant, obige Summe ist gleich $c n = P (n)$ für das Polynom $P (T) = c T$ . Dies ist bereits der Induktionsanfang.

Angenommen wir haben die Behauptung für Polynome vom Grad $d \in ℕ_{0}$ bereits bewiesen. Wir verwenden nun den Binomialsatz (Satz 3.28) für den Ausdruck

\begin{array}{l} {(T - 1)}^{d + 2} = T^{d + 2} - (\binom{d + 2}{1}) T^{d + 1} + - \dots + {(- 1)}^{d + 2} \end{array}

und erhalten

\begin{align} T^{d + 2} - {(T - 1)}^{d + 2} = (d + 2) T^{d + 1} + f (T) & (3.4) \end{align}

für ein Polynom $f (T) \in ℚ [T]$ mit Grad $d$ . Auf Grund der Induktionsannahme gibt es ein zugehöriges Polyom $F (T) \in ℚ [T]$ mit Grad $d + 1$ so dass $\sum_{k = 1}^{n} f (k) = F (n)$ für alle $n \in ℕ$ gilt. Wir summieren nun (3.4) und verwenden eine Teleskopsumme um

\begin{array}{l} n^{d + 2} & = \sum_{k = 1}^{n} (k^{d + 2} - {(k - 1)}^{d + 2}) \\ = \sum_{k = 1}^{n} ((d + 2) k^{d + 1} + f (k)) \\ = (d + 2) \sum_{k = 1}^{n} k^{d + 1} + F (n) \end{array}

und damit auch

\begin{array}{l} \sum_{k = 1}^{n} k^{d + 1} = \frac{1}{d + 2} (n^{d + 2} - F (n)) \end{array}

für alle $n \in ℕ$ zu erhalten. Da wir eine allgemeinere Induktionsvorraussetzung verwendet haben, müssen wir auch den Induktionsschritt in der gleichen Allgemeinheit zeigen.

Sei nun $p (T) \in ℚ [T]$ ein beliebiges Polynom mit Grad $d + 1$ und führendem Koeffizienten $c$ . Dann ist $q (T) = p (T) - c T^{d + 1}$ ein Polynom mit Grad $d$ . Nach Induktionsannahme gibt es daher ein Polynom $Q (T) \in ℚ [T]$ mit Grad $d + 1$ so dass $\sum_{k = 1}^{n} q (k) = Q (n)$ für alle $n \in ℕ$ gilt. Gemeinsam mit Obigem ergibt sich nun

\begin{array}{l} \sum_{k = 1}^{n} p (k) = \sum_{k = 1}^{n} (c k^{d + 1} + q (k)) = \frac{c}{d + 2} (n^{d + 2} - F (n)) + Q (n) = P (n) \end{array}

für alle $n \in ℕ$ , wobei $P (T) = \frac{c}{d + 2} (T^{d + 2} - F (T)) + Q (T) \in ℚ [T]$ Grad $d + 2$ und führenden Koeffizienten $\frac{c}{d + 2}$ hat. Dies beweist nun den Induktionsschritt und damit auch die Behauptung sowie die Proposition.

■

3.3.5 Eine Summe von Binomialkoeffizienten*

In diesem Teilabschnitt diskutieren wir in Kürze eine Summationsformel für Binomialkoeffizienten entlang von Diagonalen im Pascal Dreieck. Insbesondere ergibt sich mit dieser Summationsformel ein anderer Beweis für Proposition 3.32.

Per Definition erzeugen die Funktionen $1, x, x^{2}, \dots$ den Vektorraum $ℝ [x]$ der Polynome und bilden in der Tat sogar eine Basis von $ℝ [x]$ . Dies ist für den Polynomring Teil der Definition, und für Polynomfunktionen die Identifikation zwischen Polynome und Polynomfunktionen in Proposition 3.15. Für das Problem in Proposition 3.32 ist diese Basis jedoch nicht besonders gut geeignet. Stattdessen ist die Basis $p_{0} (x), p_{1} (x), \dots \in ℂ [x]$ definiert durch

\begin{array}{l} p_{0} (x) & = 1, \\ p_{1} (x) & = x, \\ p_{2} (x) & = \frac{x (x - 1)}{2} \end{array}

und allgemeiner durch

p_{d} (x) = \frac{1}{d!} \prod_{j = 0}^{d - 1} (x - j)

(3.5)

für alle $d \in ℕ_{0}$ deutlich besser dafür geeignet.

Übung (Eine besser geeignete Basis).

Zeigen Sie, dass die in Gleichung (3.5) definierten Polynome $p_{0}, p_{1}, p_{2}, \dots$ tatsächlich eine Basis von $ℝ [x]$ bilden.

Hinweis.

Der Grad von $p_{d}$ ist gleich $d$ für jedes $d \in ℕ$ . Die lineare Unbhängigkeit verwendet, das diese Grade alle unterschiedlich sind. Um zu zeigen, dass diese Polynome eine Basis bilden, verwendet man, dass jeder Grad auch auftritt, Division mit Rest und Induktion nach dem Grad eines darzustellenden Polynoms.

Proposition 3.33 (Summe von Binomialkoeffizienten).

Für jedes $d \in ℕ$ ist $p_{d} (x)$ ein Polynom mit rationalen Koeffizienten vom Grad $d$ , welches Leitkoeffizient $\frac{1}{d!}$ und Nullstellen $0, \dots, d - 1$ besitzt. Für jedes $d \in ℕ_{0}$ gilt des Weiteren $p_{d} (n) = (\binom{n}{d})$ für alle $n \geq d$ (siehe auch das Bild 3.4) und wir haben die Summenformel

\begin{array}{l} \sum_{k = 0}^{n} p_{d} (k) = p_{d + 1} (n + 1) \end{array}

für alle $n \in ℕ$ .

Übung.

Diese Übung liefert einen Beweis zu Proposition 3.33.

(i)

Beweisen Sie alle Behauptungen der Proposition bis auf die Summationsformel.

(ii)

Beweisen Sie die Summationsformel

\sum_{k = 0}^{n} k = \frac{n (n + 1)}{2}

für alle

n \in ℕ

mit Hilfe von folgendem Bild im Pascal Dreieck (hier für

n = 5

$PIC$

Figur 3.3: Je zwei blaue Quadrate bestimmen ein grünes und umgekehrt.

(iii)

Beweisen Sie die Summationsformel, indem Sie die Menge

𝒫

aller

(d + 1)

-elementigen Teilmengen von

{1, \dots, n + 1}

mit Hilfe des Maximums partitonieren. Sie können auch das Applet 3.34 verwenden.

Lösung.

Seien $d, n \in ℕ_{0}$ . Falls $n \in {0, \dots, d - 1}$ liegt, gilt $p_{d} (k) = 0$ für alle $k \in {0, \dots, n}$ und damit auch

p_{d + 1} (n + 1) = 0 = \sum_{k = 0}^{n} p_{d} (k) .

Wir dürfen also $n \geq d$ annehmen. Sei $𝒫$ die Menge aller $(d + 1)$ -elementigen Teilmengen von ${1, \dots, n + 1}$ . Da $A \in 𝒫$ genau $d + 1$ Elemente und nur natürliche Zahlen enthält, gilt $\max (A) \geq d + 1$ . Wir verwenden dies um

𝒫 = ⨆_{ℓ = d + 1}^{n + 1} 𝒫_{ℓ}

in die Teilmengen $𝒫_{ℓ} = {A \in 𝒫 ∣ \max (A) = ℓ}$ für $ℓ \in {d + 1, \dots, n + 1}$ zu partitionieren, so dass

(\binom{n + 1}{d + 1}) = | 𝒫 | = \sum_{ℓ = d + 1}^{n + 1} | 𝒫_{ℓ} | .

Für $ℓ \in {d + 1, \dots, n + 1}$ und eine Teilmenge $A \in 𝒫_{ℓ}$ gilt nach Definition $ℓ \in A$ und $A \subseteq {1, \dots, ℓ}$ . Entfernen wir von diesem $A$ das Element $ℓ$ , so erhalten wir eine $d$ -elementige Teilmenge $A ∖ {ℓ}$ von ${1, \dots, ℓ - 1}$ , welche eindeutig von $A$ bestimmt ist und gemeinsam mit $ℓ$ die Menge $A$ eindeutig bestimmt. Zusammenfassend bildet die Abbildung $A \mapsto A ∖ {ℓ}$ also eine Bijektion zwischen $𝒫_{ℓ}$ und den $d$ -elementigen Teilmengen von ${1, \dots, ℓ - 1}$ . Nach Übung 3.27 ergibt sich somit $| 𝒫_{ℓ} | = (\binom{ℓ - 1}{d}) = p_{d} (ℓ - 1)$ für alle $ℓ = d + 1, \dots, n + 1$ und daher

p_{d + 1} (n + 1) = (\binom{n + 1}{d + 1}) = \sum_{ℓ = d + 1}^{n + 1} (\binom{ℓ - 1}{d}) = \sum_{k = d}^{n} (\binom{k}{d}) = \sum_{k = 0}^{n} p_{d} (k),

da $p_{d} (0) = \dots = p_{d} (d - 1) = 0$ .

Applet 3.34 (Kombinatorischer Beweis).

Es wird für kleine Wahlen von $n$ und $d$ die in obigem kombinatorischem Beweis gefundene Bijektion dargestellt.

Wenn wir auf die sehr befriedigende kombinatorische Interpretation der Summenformel in Proposition 3.33 verzichten wollen, so können wir die Summenformel auch sehr einfach im Pascal-Dreieck sehen und mit Induktion beweisen.

$PIC$

Figur 3.4: Illustration der Summenformel in Proposition 3.33 für

d = 3

. In Rosa ersichtlich sind

p_{3} (k)

für

k \in {0, 1, 2, 3, 4, 5, 6}

, die summiert gerade

p_{4} (7) = (\binom{7}{4}) = 35

ergeben, wie in Grün markiert.

Übung (Summe der Binomialkoeffizienten mittels Induktion).

Beweisen Sie die letzte Aussage in Proposition 3.33 mittels vollständiger Induktion.

Übung.

Beweisen Sie Proposition 3.32 mit vollständiger Induktion wie folgt:

(i): Zeigen Sie, dass $\begin{array}{l} d! p_{d + 1} (n + 1) = \frac{1}{d + 1} n^{d + 1} + c_{d}^{'} n^{d} + \dots + c_{0}^{'} n^{0} \end{array}$
für gewisse $c_{d}^{'}, \dots, c_{0}^{'} \in ℚ$ und alle $n \in ℕ$ gilt.
(ii): Verwenden Sie Proposition 3.33 für die linke Seite von (i) und multiplizieren Sie $p_{d}$ aus.
(iii): Verwenden Sie nun die Induktionsannahme um den Beweis abzuschliessen.

3.3 Die Fakultät und der Binomialsatz

3.3.1 Fakultät

Definition 3.24 (Fakultät).

Lemma 3.25 (Kardinalität der Menge der Permutationen einer endlichen Menge).

Bemerkung.

3.3.2 Binomialkoeffizienten

Proposition 3.26 (Additionseigenschaft der Binomialkoeffizienten).

Wichtige Übung 3.27 (Kombinatorische Bedeutung der Binomialkoeffizienten).

3.3.3 Der binomische Lehrsatz

Satz 3.28 (Binomischer Lehrsatz).

Übung 3.29 (Summe der Binomialkoeffizienten).

Übung 3.30 (Eine weitere Summe).

Übung 3.31 (Das Multinomialtheorem).

3.3.4 Summen von Potenzen

Proposition 3.32 (Summe von Potenzen).

3.3.5 Eine Summe von Binomialkoeffizienten*

Übung (Eine besser geeignete Basis).

Proposition 3.33 (Summe von Binomialkoeffizienten).

Übung.

Applet 3.34 (Kombinatorischer Beweis).

Übung (Summe der Binomialkoeffizienten mittels Induktion).

Übung.

License