Summen, Produkte und vollständige Induktion – Mathe Studium 1. Semester Lernzettel zum Herunterladen als PDF

Summen- und Produktzeichen

Binomialkoeffizienten und binomischer Satz

Vollständige Induktion

Rechnen mit dem Summenzeichen

Das Summenzeichen \(\sum_{k=m}^na_k=a_m+a_{m+1}+\dots+a_n\) ist eine Abkürzung, mit der man wie mit gewöhnlichen Summen rechnen darf. Der Name des Laufindex ist gleichgültig: \(\sum_{k=1}^nk^2=\sum_{j=1}^nj^2\). Konstante Faktoren darf man herausziehen, Summen gliedweise aufspalten, und man darf die Summe an einer Stelle teilen: \(\sum_{k=1}^na_k=\sum_{k=1}^ma_k+\sum_{k=m+1}^na_k\). Besonders wichtig ist die Indexverschiebung: Ersetzt man \(k\) durch \(j+1\), so ändern sich die Grenzen in Gegenrichtung, \(\sum_{k=1}^na_k=\sum_{j=0}^{n-1}a_{j+1}\). Mit ihr bringt man zwei Summen auf denselben Index, um sie zusammenzufassen oder teleskopisch kürzen zu lassen.

Produkte und Fakultäten

Analog zum Summenzeichen schreibt man Produkte mit \(\prod_{k=m}^na_k=a_m\cdot a_{m+1}\cdots a_n\). Das wichtigste Produkt ist die Fakultät \(n!=\prod_{k=1}^nk\) mit der Vereinbarung \(0!=1\) (leeres Produkt). Logarithmieren verwandelt Produkte in Summen: \(\ln\prod a_k=\sum\ln a_k\). Auch bei Produkten gibt es ein Teleskopprinzip – Zähler und Nenner aufeinanderfolgender Faktoren kürzen sich.

Binomialkoeffizienten in der Kombinatorik

Der Binomialkoeffizient \(\binom nk=\frac{n!}{k!\,(n-k)!}\) zählt die \(k\)-elementigen Teilmengen einer \(n\)-elementigen Menge, also die Möglichkeiten, \(k\) von \(n\) Dingen ohne Beachtung der Reihenfolge auszuwählen. Daraus erklären sich seine Eigenschaften ohne Rechnung: Die Symmetrie \(\binom nk=\binom n{n-k}\) entsteht, weil die Auswahl der \(k\) Elemente zugleich die Auswahl der \(n-k\) nicht gewählten ist. Die Rekursion \(\binom{n+1}k=\binom nk+\binom n{k-1}\), die das Pascalsche Dreieck erzeugt, unterscheidet, ob ein bestimmtes Element dabei ist oder nicht. Und \(\sum_k\binom nk=2^n\) zählt alle Teilmengen.

Varianten der Induktion

Die Induktion muss nicht bei \(1\) beginnen: Gilt die Aussage für \(n_0\) und folgt sie aus der für \(n\) für alle \(n\ge n_0\), so gilt sie für alle \(n\ge n_0\). Bei der starken Induktion darf man im Induktionsschritt alle Aussagen \(A(n_0),\dots,A(n)\) voraussetzen, nicht nur \(A(n)\). Das braucht man etwa für die Zerlegung in Primfaktoren oder für Rekursionen, die auf mehrere Vorgänger zugreifen, wie die Fibonacci-Folge. Viele Formeln, die man vermutet, entstehen durch Ausprobieren kleiner Fälle; die Induktion liefert dann den Beweis.

Doppelsummen und Summationsreihenfolge

Summen über zwei Indizes treten bei Tabellen, Matrizen und Wahrscheinlichkeiten auf. Bei einer endlichen Doppelsumme darf man die Reihenfolge vertauschen: \(\sum_{i=1}^m\sum_{j=1}^na_{ij}=\sum_{j=1}^n\sum_{i=1}^ma_{ij}\), denn beide Seiten addieren alle Einträge einer Tabelle, einmal zeilenweise und einmal spaltenweise. Hängt die Grenze des inneren Index vom äußeren ab, muss man beim Vertauschen die Grenzen neu bestimmen. Ein Bild der Indexmenge hilft: \(\sum_{i=1}^n\sum_{j=1}^ia_{ij}\) läuft über das Dreieck \(1\le j\le i\le n\), und dasselbe Dreieck wird durch \(\sum_{j=1}^n\sum_{i=j}^na_{ij}\) beschrieben.

Rekursiv definierte Folgen

Viele Folgen sind rekursiv gegeben: Man kennt den Anfang und eine Vorschrift, wie man aus einem Glied das nächste berechnet. Die Induktion ist das natürliche Werkzeug, um für solche Folgen eine geschlossene Formel zu beweisen. Typisch ist der Dreischritt: einige Glieder ausrechnen, ein Muster vermuten und die Vermutung durch Induktion bestätigen. So erhält man etwa für \(a_1=1\), \(a_{n+1}=a_n+2n+1\) die Werte \(1,4,9,16,\dots\), vermutet \(a_n=n^2\) und bestätigt dies mit \(n^2+2n+1=(n+1)^2\). Auch Ungleichungen zwischen Folgengliedern, Schranken und Monotonie zeigt man häufig auf diesem Weg.