Das Rechnen mit Zahlen, wie Sie es auch aus der Schule kennen, gründet sich auf folgende Regeln:
Definition (Körperaxiome). Ein Körper ist eine Menge \(K\), versehen mit Abbildungen \[+:K\times K\to K\qquad\qquad \cdot:K\times K\to K,\] welche Addition und Multiplikation genannt werden, die folgenden Regeln gehorchen:
a + b = b+a,\qquad\qquad a\cdot b=b\cdot a.$$
(a+b)+c=a+(b+c),\qquad\qquad (a\cdot b)\cdot c= a\cdot (b\cdot c).
$$
a\cdot (b+c)= a\cdot b + a\cdot c.$$
a+0=a\quad , \quad a \cdot 1=a.$$
a+(-a)=0\quad , \quad a\cdot\frac{1}{a}=1.$$
Diese Regeln sollen natürlich für alle Elemente \(a,b,c\in K\) gelten. Die natürlichen Zahlen erfüllen diese Wunschliste fast vollständig. Wenn wir ihnen eine Null spendieren, fehlen einzig die Inversen. Den ganzen Zahlen fehlen die multiplikativen Inversen. Die rationalen, wie auch die reellen Zahlen (hier verweise ich auf Ihr Schulwissen) bilden Körper. Die kleinste Menge, auf der man Addition und Multiplikation derart definierten kann, so dass sie einen Körper formt, besteht aus zwei Elementen, nämlich $$\mathbb F_2=\{0,1\}.$$
Aus den Rechenregeln 1 bis 5 folgen schon die meisten Regeln, nach denen man zu rechnen gewohnt ist. Hier zwei Beispiele:
- Ein Produkt verschwindet dann und nur dann, wenn mindestens einer der Faktoren verschwindet (Beweisen Sie diese Aussage als Übung!).
- Eine Summe (bzw. ein Produkt) von mehreren Zahlen ist unabhängig von der Reihenfolge der Summanden (bzw. Faktoren) und von der Art der Zusammenfassung. Beispielsweise gilt $$
(a+b)+(c+d)=(a+(b+c))+d,\qquad\qquad a\cdot(b\cdot c)=(c\cdot
a)\cdot b. $$ Man kann sich also die Klammern, mit denen die Reihenfolge der Verknüpfungen gekennzeichnet wird, ersparen und schreibt einfach \(a+b+c+d\) bzw. \(abc\).
Für das Produkt von \(n\) Kopien des gleichen Faktors führt man als Abkürzung die Potenz$$
a^n:= \underbrace {a\cdot a\cdot\ldots\cdot a}_{n-{\rm mal}}
$$ mit Basis \(a\) und Exponenten \(n\) ein. Für diese gelten die Potenzgesetze
$$a^m\cdot a^n=a^{m+n},\quad
(ab)^n=a^n b^n,\quad (a^m)^n=a^{m\, n}.$$ Zunächst sind Potenzen nur für natürliche Zahlen als Exponenten definiert. Für \(a\ne 0\) lassen sich die Potenzen auch für ganzzahlige Exponenten definieren, indem man setzt \(a^0=1,\quad a^{-n}=\frac{1}{a^n}\) für \(n \in\mathbb N\). Die drei Formeln sind dann auch für diesen erweiterten Potenzbegriff richtig. Für \(a=0\) ist es Konvention, \(0^0=1\) zu setzen. Damit bleiben \(0^{-1}, 0^{-2}\) undefiniert, da das ohne Verletzung der Potenzgesetze nicht mehr geht.
Multipliziert man eine Potenz \((a+b)^n\) aus, so ergibt sich eine Summe, in der Ausdrücke der Form \(a^{n-k}\,b^k\) mit \(k\) zwischen \(0\) und \(n\) jeweils mit einer gewissen Vielfachheit auftauchen. Multipliziert man \((a+b)^n\) noch einmal mit \((a+b)\), so ergibt sich: Die Vielfachheit, mit der \(a^{n+1-k}\,b^k\) in \((a+b)^{n+1}\) auftaucht, ist die Summe der Vielfachheiten, mit der \(a^{n+1-k}\,b^{k-1}\) und \(a^{n-k}\, b^k\) jeweils in \((a+b)^n\) auftauchen. Diese Vielfachheiten erhält man also aus dem sogenanntenPascalschen Dreieck, in dem jede Zahl gleich die Summe der beiden schräg über ihr stehenden ist
$$
\begin{matrix}
&&&&1&&&&\cr
&&&1&&1&&&\cr
&&1&&2&&1&&\cr
&1&&3&&3&&1&\cr
\phantom{\dots}1&&4&&6&&4&&1\phantom{\dots}\cr
\dots&\dots&&\dots&&\dots&&\dots&\dots
\end{matrix}
$$
Die Vielfachheiten lassen sich auch explizit bestimmen: Wir zählen ab, wie oft der Ausdruck $a^{n-k}\, b^k$ im $n$-fachen Produkt $(a+b)^n$ vorkommt. Zur Veranschaulichung setzen wir die Kommutativität der Multiplikation zuerst einmal außer Kraft. Dann erhalten wir $$(a+b)^2=(a+b)(a+b)=a^2+ab +ba+bb.$$ Den Summanden $ab$ erhalten wir, wenn wir das $a$ im ersten Faktor $(a+b)$ mit dem $b$ aus dem zweiten Faktor $(a+b)$ multiplizieren, den Summanden $ba$ entsprechend aus der Multiplikation des $b$'s aus dem ersten Faktor mit dem $a$ aus dem zweiten Faktor. Analog erhalten wir $$ (a+b)^3=aaa+(aab+aba+baa)+(abb+bab+bba)+bbb$$ $$\begin{equation}\begin{split} (a+b)^4=aaaa&+(aaab+aaba+abaa+baaa)+(aabb+abab+abba+baab+baba+bbaa)\\&+(abbb+babb+bbab+bbba)+bbbb.\end{split}\end{equation}$$ Auf diese Weise können wir bei jedem Summanden wie etwa $$abbabbaaaabbaabbbbababaab$$ eindeutig zurückverfolgen, welche Wahl von Summanden in jedem einzelnen Faktor der Form \((a+b)\) zur Entstehung genau dieses Terms geführt hat. Um den Koeffizienten des Ausdrucks $a^{n-k}\, b^k$ zu bestimmen, müssen wir ermitteln, wie viele verschiedene Wörter der Länge $n$ wir aus $(n-k)$ Exemplaren des Buchstabens $a$ und $k$ Exemplaren des Buchstabens $b$ bilden können. Solche Wörter sind aber eindeutig durch die $k$ Stellen festgelegt, an denen der Buchstabe $b$ zu stehen kommt.
Zur Ermittlung dieser Zahl gehen wir in zwei Schritten vor. Im ersten Schritt versehen wir jedes $b$ zusätzlich mit einem Index. Wir betrachten also Buchstaben $b_1,b_2,\ldots,b_k$, die wir der Reihe nach auf $n$ Stellen verteilen wollen. Für $b_1$ haben wir die Auswahl von $n$ Stellen. Danach ist die gewählte Stelle besetzt. Für $b_2$ gibt es dann nur noch eine Wahl aus $(n-1)$ Stellen. Und so weiter. Insgesamt gibt es $n(n-1)\cdot\ldots\cdot(n-k+1)$ Möglichkeiten, diese indizierten $b$'s auf $n$ Stellen zu verteilen. Die unbesetzten Stellen füllen wir mit $a$'s.
Wenn man die $b$'s auf diese Weise verteilt, erhält man nach Löschen der Indizes jedes Wort allerdings mehrmals, nämlich so oft, sie man $k$ Indizes auf die $b$'s in einem derart konstruierten Wort verteilen kann: Für den Index $1$ gibt es $k$ Möglichkeiten, für die $2$ gibt es $(k-1)$ Möglichkeiten. Und so weiter. Insgesamt sind es derer $k(k-1)\cdot\ldots\cdot1$ Stück. Dieses Produkt wird abkürzend $k$ Fakultät genannt und mit
$$
\quad k(k-1)\cdot\ldots\cdot2\cdot1= k!
$$ bezeichnet. Insgesamt hat man nun die Zahl $n(n-1)\cdot\ldots\cdot(n-k+1)$ von Verteilungen von indizierten $b$'s noch durch die Anzahl $k!$ der möglichen Verteilung der $k$ Indizes auf die angordneten $b$'s zu teilen. Für diesen Quotienten, den Binomialkoeffizienten, schreibt man
$${n\choose k}:=\frac{n!}{(n-k)!\;k!}$$ und liest $n$ über $k$. Wir folgern:
1.4.1. Binomischer Satz. Für alle natürlichen Zahlen $n\in\mathbb N$ gilt die Gleichung
$$
(a+b)^n=a^n+{n\choose 1}a^{n-1}b+
{n\choose 2}a^{n-2}b^2+\ldots+{n\choose n-1}a\;b^{n-1}+b^n.
$$
Wenn eine mathematische Aussage als Satz hingestellt wird, soll das zum Einen besagen, dass diese Aussage als bedeutsam oder nützlich betrachtet wird. Zum Anderen wird damit betont, dass die Aussage nicht als völlig offensichtlich angesehen wird, sondern einer überzeugenden Begründung bedarf. Eine solche Begründung wird mit einem Beweis geliefert.
Aber habe ich bei der Herleitung des binomischen Satzes keine ausreichende Begründung gegeben? Der obige Beweis ist wohl akzeptabel. Mit einigen Aspekten bin ich aber unzufrieden.
- In der ersten Stunde habe ich betont, Mathematik spiele sich nur in unseren Gedanken ab und wir müssten vorsichtig sein, nicht in Widersprüche zu geraten. Zum Rechnen in Körpern haben wir uns oben fünf Rechenregeln gegeben, von denen wir ausgehen wollen. Wenn wir also etwas begründen, sollten wir diese Rechenregeln und unser Konzept der Zahlen benutzen. Statt dessen habe ich an die Intuition appelliert (wir ermitteln, wie viele verschiedene Wörter der Länge $n$ wir aus $(n-k)$ Exemplaren des Buchstabens $a$ $\ldots$) und neue Begrifflichkeiten (Wörter, Buchstaben, Stellen, Anordnung $\ldots$) aus dem Ärmel gezaubert. Wir sollten uns lieber an die selbst gegebenen Spielregeln halten.
- Der zweite Aspekt ist ein eher pragmatischer: Wir wollen ja nicht jedesmal, wenn wir neuen Zahlen begegnen (reellen Zahlen, komplexen Zahlen, dem ominösen Körper $\mathbb {F}_2$ mit zwei Elementen oder was da noch so kommen mag), uns von Neuem überlegen, wie wir den Ausdruck $(a+b)^n$ auflösen können.
- Wenn ich mir den Ausdruck $${n\choose k}:=\frac{n!}{(n-k)!\;k!}$$ näher betrachte, so ist dies offenbar eine rationale Zahl. Dass sich alle im Nenner auftauchenden Faktoren auch wegkürzen, ist beileibe nicht offensichtlich. Die Zahl $n= \underbrace {1+1+\ldots +1}_{n-{\rm mal}}$ ist in jedem Körper definiert, somit auch $n!$. Was allerdings passieren kann, ist dass $k!$ verschwindet (z.B. gilt $n!=0\in\mathbb{F}_2$ für jedes $n\ge 2$), der Nenner in ${n\choose k}$ also Null wird. Wollten wir die Definition $${n\choose k}:=\frac{n!}{(n-k)!\;k!}$$ in einem beliebigen Körper verwendeten, so kämen wir in Erklärungsnot.
Wir können diese Schwierigkeit allerdings vermeiden, indem wir das Pascalsche Dreieck benutzen. Nach den Überlegungen zum Pascalschen Dreieck muss wohl gelten
$$
{n+1\choose k}={n\choose k-1}+{n\choose k}.
$$ Dies können wir aus der Definition direkt nachrechnen
$$\begin{eqnarray*}
\frac{(n+1)n \ldots (n-k+2)}{k(k-1)\ldots 1}&=&[(n-k+1)+k]\;
\frac{n(n+1)\ldots(n-k+2)}{k(k-1)\ldots
1}\\
&=&\frac{n(n+1)\ldots(n-k+1)}{k(k-1)\ldots
1}\;+\;\frac{n(n-1)\ldots(n-k+2)}{(k-1)\ldots 1}.
\end{eqnarray*}$$
Im Pascalschen Dreieck wird ${n\choose k}$ rekursiv definiert: Wir setzen ${1\choose 0}={1\choose 1}=1$. Unter der Annahme, ${n\choose k}$ sei definiert für alle $k$ zwischen Null und $n$, definieren wir ${n+1\choose
0}={n+1\choose n+1}=1$ und für alle $k$ zwischen $1$ und $n$ setzen wir ${n+1\choose k}:={n\choose k-1}+{n\choose k}$. Auf diese Weise ist ${n\choose k}$ in jedem Körper definiert.
Beweis des binomischen Satzes.
- Induktionsanfang: Die Aussage gilt für $n=1$:
$$
(a+b)^1=a^1+b^1.
$$ - Induktionsannahme: Wir nehmen an, die Aussage gelte für $n$, d.h. es gelte
$$
(a+b)^n=a^n+{n\choose 1}a^{n-1}b+{n\choose 2}a^{n-2}b^2+\ldots
+{n\choose n-2}a^2 b^{n-2}+{n\choose n-1}a\; b^{n-1}+b^n
$$ - Induktionsschluss:$$\begin{eqnarray*}
(a+b)^{n+1}&=&(a+b)^n(a+b)\\
&=&\left(a^n+{n\choose 1}a^{n-1} b+\ldots +{n\choose
n-1}a\;b^{n-1}+b^n\right)(a+b)\\
&=&a^{n+1}+\left(1+{n\choose
1}\right)a^n b +\left({n\choose 1}+{n\choose 2}\right)a^{n-1}b^2+\ldots + \left({n\choose n-1}+1\right) a\;b^n+b^{n+1}\\
&=&a^{n+1}+{n+1\choose 1}a^n b+{n+1\choose
2}a^{n-1} b^2 +\ldots + {n+1\choose n}a\;b^n+b^{n+1}
\end{eqnarray*}$$
qed
Hier ein weiteres Beispiel für vollständige Induktion:
1.4.2. Satz. Es gilt, falls $n$ eine natürliche Zahl und $a\neq 1$ ist:$$
1+a+a^2+\ldots + a^{n-1}=\frac{1-a^n}{1-a}.
$$
Beweis.
- Induktionsanfang:$$
1=\frac{1-a}{1-a}
$$ - Induktionsschluss:
$$
1+a+a^2+\ldots+a^n=\frac{1-a^n}{1-a}+a^n=\frac{1-a^n}{1-a}+\frac{(1-a)a^n}{1-a}=\frac{1-a^{n+1}}{1-a}.
$$
qed
Die Induktionsbehauptung habe ich im Beweis weggelassen, da sie ja nur die Aussage, die ich im Satz behauptet habe, wiederholt.
In diesen Formeln und auch später kommen häufig Summen von mehreren Gliedern vor. Man führt folgende Abkürzung ein: Sind $k$ und $l$ ganze Zahlen, $l$ größer als $k$, und $a_k,a_{k+1},\ldots,a_l$ beliebige Zahlen, so schreibt man
$$
\sum_{i=k}^l\; a_i=a_k+a_{k+1}+\ldots+a_l
$$ und liest Summe $a_i$ über $i$ von $k$ bis $l$.
Die binomische Formel lautet in dieser Schreibweise:
$$
(a+b)^n=\sum_{k=0}^n {n\choose k}a^{n-k}\;b^k
$$ und die obige Summe
$$
\sum_{k=0}^{n-1}\;a^k=\frac{1-a^n}{1-a}\quad,\quad {\rm falls}\quad
a \ne 1\quad {\rm ist}.
$$
Kompliziertere Summen, wenn z.B. über zwei Indizes summiert wird:
$$
\left(\sum_{k=1}^m a_k\right)\left(\sum_{l=1}^n b_l\right)=\sum_{k=1}^m \left(\sum_{l=1}^n a_k\;b_l\right),
$$
schreibt man auch so, dass nur ein Summenzeichen verwendet wird:
$$
\sum_{\substack{k=1,\ldots,m\\ l=1,\ldots,n}}a_k\;b_l.
$$
Entsprechendes gilt für Produkte: Man schreibt
$$
a_k a_{k+1}\ldots a_l= \prod_{i=k}^l a_i
$$
und liest Produkt $a_i$ über $i$ von $k$ bis $l$.
Beispiel:
$$ n!=\prod_{k=1}^n k.
$$