Zum Inhalt springen
Topos Uranos
Deutsch

Summen, arithmetische und geometrische Folgen und Induktion

Zusammenfassung

Diese Lektion führt das Summenzeichen und seine Eigenschaften ein (Linearität, Zerlegung, Indexverschiebung und Umkehrung der Reihenfolge) und wendet es auf die Berechnung von Teleskopsummen und der Summen arithmetischer und geometrischer Folgen an. Danach untersucht sie die starke Induktion und das Wohlordnungsprinzip, beweist, dass die Induktion beide impliziert, präzisiert, in welchem Sinn sie zu ihr äquivalent sind, und verwendet sie, um zu beweisen, dass jede natürliche Zahl größer als 11 ein Produkt von Primzahlen ist.

Lernziele

  1. Summen mit dem Summenzeichen schreiben und umformen und dabei seine Eigenschaften der Linearität, der Zerlegung, der Indexverschiebung und der Umkehrung der Reihenfolge anwenden.
  2. Teleskopsummen berechnen und sie verwenden, um Summenformeln herzuleiten und nicht nur zu überprüfen.
  3. Den allgemeinen Term und die Summe der ersten Terme einer arithmetischen oder geometrischen Folge bestimmen und sie auf das Lösen von Aufgaben anwenden.
  4. Mit der starken Induktion und mit dem Wohlordnungsprinzip beweisen, beide aus dem Induktionsprinzip herleiten und erklären, mit welchen zusätzlichen Tatsachen die Wohlordnung die Induktion zurückzugewinnen erlaubt.

Das Summenzeichen

In der Lektion über die Peano-Axiome traten Summen vieler Terme auf, die einer Regel folgen, etwa 1+2+⋯+n1 + 2 + \cdots + n. Die Auslassungspunkte überlassen es dem Leser, diese Regel zu erraten; das Summenzeichen spricht sie aus. Sind am,am+1,…,ana_m, a_{m + 1}, \ldots, a_n Zahlen, mit m≤nm \leq n, so schreibt man

∑k=mnak=am+am+1+⋯+an\sum_{k=m}^{n} a_k = a_m + a_{m + 1} + \cdots + a_n

und liest „die Summe der aka_k für kk von mm bis nn“. Der Buchstabe kk ist der Index der Summe; mm und nn sind ihre untere und obere Grenze, und aka_k ist der allgemeine Term. Die Summe hat n−m+1n - m + 1 Terme. Der Index ist eine gebundene Variable: Der Wert der Summe hängt nicht von dem Buchstaben ab, mit dem man ihn bezeichnet, sodass ∑k=1nk2\sum_{k=1}^{n} k^2 und ∑j=1nj2\sum_{j=1}^{n} j^2 dieselbe Zahl sind. Der Index durchläuft natürliche Zahlen; die Terme dagegen können Zahlen anderer Art sein. In dieser Lektion treten außer natürlichen Zahlen auch ganze Zahlen mit ihren negativen und Brüche auf, die die nächste Einheit konstruiert: Hier werden sie vorweggenommen, und von ihnen werden nur die elementaren Rechen- und Ordnungsregeln verwendet (Kommutativität, Assoziativität, Distributivität, die Vorzeichenregeln, die Subtraktion und die Division durch eine von null verschiedene Zahl). Die folgenden Eigenschaften des Summenzeichens werden mit diesen Regeln bewiesen und gelten daher für Terme jeder dieser Arten.

Wie die Addition, die Multiplikation und die Potenz in der Lektion über die Grundrechenarten mit natürlichen Zahlen lässt die Summe eine rekursive Definition zu, die ohne Auslassungspunkte auskommt: Die Summe aus einem einzigen Term ist dieser Term, und um einen Term hinzuzufügen, addiert man ihn zum vorigen Ergebnis.

∑k=mmak=am,∑k=mn+1ak=∑k=mnak+an+1\sum_{k=m}^{m} a_k = a_m, \qquad \sum_{k=m}^{n + 1} a_k = \sum_{k=m}^{n} a_k + a_{n + 1}

Diese Definition beginnt bei mm, während der Rekursionssatz, so wie er formuliert wurde, Funktionen ab 11 definiert. Es genügt jedoch, den Index zu verschieben: Statt der Summe bis nn definiert man die Summe der ersten qq Terme ab ama_m. Mit dem Anfangswert ama_m und der Regel gq(x)=x+am+qg_q(x) = x + a_{m + q} liefert der Rekursionssatz eine eindeutige Funktion FF von N\mathbb{N} in die Zahlen mit F(1)=amF(1) = a_m und F(q+1)=F(q)+am+qF(q + 1) = F(q) + a_{m + q} für jede natürliche Zahl qq. Für n≥mn \geq m definiert man dann die Summe bis nn als den Wert von FF an der Anzahl ihrer Terme, n−m+1n - m + 1, die eine natürliche Zahl ist, weil m<n+1m < n + 1:

∑k=mnak=F(n−m+1)\sum_{k=m}^{n} a_k = F(n - m + 1)

Mit n=mn = m erhält man F(1)=amF(1) = a_m, und mit q=n−m+1q = n - m + 1 ist wegen m+q=n+1m + q = n + 1 die Gleichung F(q+1)=F(q)+am+qF(q + 1) = F(q) + a_{m + q} genau die zweite Regel der Definition. Folglich bestimmt die rekursive Definition ab mm für jedes n≥mn \geq m eine eindeutige Summe, und im Fall m=1m = 1 stimmt sie mit der überein, die der Rekursionssatz direkt liefert, denn dann ist F(n)=∑k=1nakF(n) = \sum_{k=1}^{n} a_k.

Mit dieser Schreibweise lautet die in der Lektion über die Peano-Axiome durch Induktion bewiesene Formel für die Summe der ersten nn natürlichen Zahlen so:

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

Die Summe der Quadrate, ∑k=1nk2\sum_{k=1}^{n} k^2, ist der nächste Schritt, und diese Lektion wird sich nicht darauf beschränken, sie zu überprüfen: Der Abschnitt über die Teleskopsummen leitet sie her, ohne sie vorher zu kennen.

Induktionen über die obere Grenze einer Summe beginnen bei der unteren Grenze mm, die nicht 11 sein muss. Das Induktionsprinzip der Peano-Axiome beginnt jedoch bei 11; um bei einer anderen natürlichen Zahl zu beginnen, braucht man das folgende Lemma.

LemmaInduktion ab einer beliebigen natürlichen Zahl

Sei n0n_0 eine natürliche Zahl. Gilt eine Eigenschaft für n0n_0, und gilt sie, sobald sie für eine beliebige natürliche Zahl k≥n0k \geq n_0 gilt, auch für k+1k + 1, so gilt diese Eigenschaft für alle natürlichen Zahlen n≥n0n \geq n_0. Die Idee ist, die natürlichen Zahlen ab n0n_0 neu zu nummerieren, um zum gewöhnlichen Induktionsprinzip zurückzukehren. Verwendet werden das Lemma aus der Lektion über die Grundrechenarten mit natürlichen Zahlen, nach dem jede von 11 verschiedene natürliche Zahl ein Nachfolger ist, und die Monotonie der Addition. In der Abbildung ist n0=4n_0 = 4 und p=3p = 3: Unter jeder natürlichen Zahl ab n0n_0 steht ihre neue Nummer qq.

Beweis

  1. n0=p+1,Q(q)↔P(p+q)n_0 = p + 1, \quad Q(q) \leftrightarrow P(p + q)

    Ist n0=1n_0 = 1, so ist es das Induktionsprinzip. Andernfalls ist n0=p+1n_0 = p + 1 für eine natürliche Zahl pp, und wir betrachten die Eigenschaft QQ, die PP für p+qp + q behauptet.

  2. Q(1)↔P(p+1)↔P(n0)Q(1) \leftrightarrow P(\resaltar{p + 1}) \leftrightarrow P(\resaltar{n_0})

    Die Eigenschaft QQ gilt für 11, weil Q(1)Q(1) dasselbe ist wie P(n0)P(n_0).

  3. P(p+q)→P((p+q)+1)=P(p+(q+1))P(p + q) \rightarrow P(\resaltar{(p + q) + 1}) = P(\resaltar{p + (q + 1)})

    Gilt Q(q)Q(q), so ist wegen 1≤q1 \leq q nach der Monotonie der Addition p+q≥p+1=n0p + q \geq p + 1 = n_0, und der vorausgesetzte Schritt lässt sich auf k=p+qk = p + q anwenden: Q(q+1)Q(q + 1) gilt.

  4. n≥n0→(∃q∈N)(n=p+q)n \geq n_0 \rightarrow (\exists q \in \mathbb{N})(n = p + q)

    Nach dem Induktionsprinzip gilt Q(q)Q(q) für jedes qq. Jedes n≥n0n \geq n_0 hat die Form p+qp + q: im Fall n=n0n = n_0 mit q=1q = 1, und im Fall n=n0+ln = n_0 + l mit q=1+lq = 1 + l.

Eigenschaften des Summenzeichens

Aus der rekursiven Definition folgen durch Induktion über die obere Grenze die folgenden Eigenschaften, die für beliebige Terme aka_k und bkb_k und für jede Zahl cc gelten:

  1. Linearität: ∑k=mn(ak+bk)=∑k=mnak+∑k=mnbk\sum_{k=m}^{n} (a_k + b_k) = \sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k und ∑k=mnc ak=c∑k=mnak\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k. Insbesondere heißt eine Konstante nn-mal addieren, sie mit nn zu multiplizieren: ∑k=1nc=nc\sum_{k=1}^{n} c = nc.
  2. Zerlegung: Ist m≤p<nm \leq p < n, so ist ∑k=mnak=∑k=mpak+∑k=p+1nak\sum_{k=m}^{n} a_k = \sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k.
  3. Indexverschiebung: Für jede natürliche Zahl pp ist ∑k=mnak=∑j=m+pn+paj−p\sum_{k=m}^{n} a_k = \sum_{j=m+p}^{n+p} a_{j - p}.
  4. Umkehrung der Reihenfolge: ∑k=1nak=∑j=1nan+1−j\sum_{k=1}^{n} a_k = \sum_{j=1}^{n} a_{n + 1 - j}.
SatzEigenschaften des Summenzeichens

Für beliebige Terme aka_k und bkb_k und für jede Zahl cc ist das Summenzeichen linear, zerfällt in zwei aufeinanderfolgende Summen und lässt die Indexverschiebung und die Umkehrung der Reihenfolge zu, im Sinne der vorigen Liste. Jede Eigenschaft wird durch Induktion über die obere Grenze bewiesen, die dank des vorigen Lemmas bei der unteren beginnt. Verwendet werden nur die rekursive Definition und die Eigenschaften der Addition und der Multiplikation; die Umkehrung stützt sich außerdem auf die Zerlegung und die Verschiebung.

Beweis

  1. ∑k=mn+1(ak+bk)=∑k=mnak+∑k=mnbk+(an+1+bn+1)=∑k=mn+1ak+∑k=mn+1bk\sum_{k=m}^{n + 1} (a_k + b_k) = \resaltar{\sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k} + (a_{n + 1} + b_{n + 1}) = \sum_{k=m}^{n + 1} a_k + \sum_{k=m}^{n + 1} b_k

    Linearität. Für n=mn = m haben beide Seiten den Wert am+bma_m + b_m. Gilt sie für nn, so wendet man die rekursive Definition, die Induktionsvoraussetzung sowie die Assoziativität und die Kommutativität der Addition an. Ebenso beweist man mit der Distributivität, dass ∑k=mnc ak=c∑k=mnak\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k ist, und dass ∑k=1nc=nc\sum_{k=1}^{n} c = nc ist, weil nc+c=(n+1)cnc + c = (n + 1)c.

  2. ∑k=mp+1ak=∑k=mpak+ap+1=∑k=mpak+∑k=p+1p+1ak\sum_{k=m}^{p + 1} a_k = \sum_{k=m}^{p} a_k + \resaltar{a_{p + 1}} = \sum_{k=m}^{p} a_k + \resaltar{\sum_{k=p+1}^{p + 1} a_k}

    Zerlegung, bei festem pp, durch Induktion über nn ab p+1p + 1. Für n=p+1n = p + 1 ist es die rekursive Definition, weil die Summe aus einem einzigen Term dieser Term ist.

  3. ∑k=mn+1ak=∑k=mpak+∑k=p+1nak+an+1=∑k=mpak+∑k=p+1n+1ak\sum_{k=m}^{n + 1} a_k = \resaltar{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k} + a_{n + 1} = \dato{d}{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n + 1} a_k}

    Gilt die Zerlegung für nn, so addiert man den Term an+1a_{n + 1} auf beiden Seiten und wendet auf jede Summe die rekursive Definition an.

  4. ∑j=m+pn+1+paj−p=∑j=m+pn+paj−p+an+1=∑k=mnak+an+1=∑k=mn+1ak\sum_{j=m+p}^{n+1+p} a_{j - p} = \resaltar{\sum_{j=m+p}^{n+p} a_{j - p}} + a_{n + 1} = \resaltar{\sum_{k=m}^{n} a_k} + a_{n + 1} = \dato{s}{\sum_{k=m}^{n + 1} a_k}

    Verschiebung. Für n=mn = m haben beide Seiten den Wert ama_m. Gilt sie für nn, so wendet man, da die obere Grenze (n+p)+1(n + p) + 1 gleich (n+1)+p(n + 1) + p ist, die rekursive Definition und die Induktionsvoraussetzung an.

  5. ∑j=1n+1an+2−j=an+1+∑j=2n+1an+2−j=an+1+∑i=1nan+1−i\sum_{j=1}^{n + 1} a_{n + 2 - j} = a_{n + 1} + \resaltar{\sum_{j=2}^{n + 1} a_{n + 2 - j}} = a_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}}

    Umkehrung, durch Induktion über nn. Für n=1n = 1 haben beide Seiten den Wert a1a_1. Gilt sie für nn, so spaltet man von der umgekehrten Summe aus n+1n + 1 Termen durch die Zerlegung den ersten Term ab und verschiebt den Index um eins, mit j=i+1j = i + 1.

  6. an+1+∑i=1nan+1−i=an+1+∑k=1nak=∑k=1n+1aka_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}} = a_{n + 1} + \resaltar{\sum_{k=1}^{n} a_k} = \sum_{k=1}^{n + 1} a_k

    Nach der Induktionsvoraussetzung hat die letzte Summe den Wert ∑k=1nak\sum_{k=1}^{n} a_k; mit der Kommutativität und der rekursiven Definition erhält man die Umkehrung für n+1n + 1.

Die Linearität erlaubt es, eine komplizierte Summe auf bekannte Summen zurückzuführen. Die beiden letzten Eigenschaften sind Variablenwechsel: Die Verschiebung setzt k=j−pk = j - p ein und durchläuft dieselben Terme mit einer anderen Nummerierung, und die Umkehrung setzt k=n+1−jk = n + 1 - j ein und durchläuft sie vom letzten bis zum ersten. Mit dem Produkt verhält sich das Summenzeichen jedoch nicht ebenso: Die Summe der Produkte ist nicht das Produkt der Summen. Es genügt ein Beispiel mit zwei Termen und ak=bk=ka_k = b_k = k:

∑k=12k⋅k=1+4=5≠9=(1+2)(1+2)\sum_{k=1}^{2} k \cdot k = 1 + 4 = 5 \neq 9 = (1 + 2)(1 + 2)
PropositionDie Summe der ersten ungeraden Zahlen

Man beweise, dass die Summe der ersten nn ungeraden Zahlen n2n^2 ist. Die Linearität führt die Summe auf zwei andere, schon bekannte zurück, ohne dass eine neue Induktion nötig ist.

Beweis

  1. 1+3+5+⋯+(2n−1)=∑k=1n(2k−1)1 + 3 + 5 + \cdots + (2n - 1) = \dato{s}{\sum_{k=1}^{n} (2k - 1)}

    Die ungerade Zahl an der Stelle kk ist 2k−12k - 1: Die erste ist 11, die zweite 33 und die an der Stelle nn ist 2n−12n - 1. Die gesuchte Summe schreibt sich so.

  2. ∑k=1n(2k−1)=2∑k=1nk−∑k=1n1\sum_{k=1}^{n} \resaltar{(2k - 1)} = \resaltar{2 \sum_{k=1}^{n} k - \sum_{k=1}^{n} 1}

    Wegen der Linearität zerfällt die Summe in zwei: das Doppelte der Summe der kk, minus die Summe von nn Einsen.

  3. 2∑k=1nk−∑k=1n1=n(n+1)−n2 \resaltar{\sum_{k=1}^{n} k} - \resaltar{\sum_{k=1}^{n} 1} = \resaltar{n(n + 1)} - \resaltar{n}

    Die erste Summe ist die der ersten nn natürlichen Zahlen, n(n+1)2\frac{n(n + 1)}{2}, und der Faktor 22 kürzt ihren Nenner; die zweite addiert nn-mal die Zahl 11.

  4. n(n+1)−n=n2+n−n=n2\resaltar{n(n + 1)} - n = \resaltar{n^2 + n} - n = n^2

    Wir multiplizieren das Produkt aus; die Terme nn und −n-n heben sich auf.

  5. k2−(k−1)2=2k−1k^2 - (k - 1)^2 = 2k - 1

    Die Abbildung zeigt den Grund: Jede ungerade Zahl ist die Differenz zweier aufeinanderfolgender Quadratzahlen, der Gnomon, der das Quadrat mit der Seite k−1k - 1 in das mit der Seite kk verwandelt.