Lektion 1.3

Vollständige Induktion

45 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • das Prinzip der vollständigen Induktion formulieren und mit dem Wohlordnungsprinzip begründen,

  • Summenformeln, Ungleichungen und Teilbarkeitsaussagen mit Induktionsanfang und Induktionsschritt beweisen,

  • rekursiv definierte Folgen in eine geschlossene Formel übersetzen und diese beweisen,

  • die starke Induktion einsetzen, wenn der Schritt mehr als den direkten Vorgänger braucht,

  • fehlerhafte Induktionsbeweise erkennen und den Fehler benennen.

Vorausgesetzt: Betrag, Dreiecksungleichung und Ungleichungen, Grundlegende Beweistechniken

Wer die ersten ungeraden Zahlen der Reihe nach addiert, erhält immer eine Quadratzahl: 1=11 = 1, 1+3=41 + 3 = 4, 1+3+5=91 + 3 + 5 = 9, 1+3+5+7=161 + 3 + 5 + 7 = 16. Gilt das für alle Anzahlen von Summanden, auch für eine Million?

Du kannst noch so viele Fälle nachrechnen, für alle unendlich vielen natürlichen Zahlen schaffst du es nicht. Und Beispiele können täuschen. Der Term n2+n+41n^2 + n + 41 liefert für n=0,1,2,…,39n = 0, 1, 2, \dots, 39 lauter Primzahlen: 41,43,47,53,…41, 43, 47, 53, \dots Wer nach vierzig Treffern aufhört, wäre sich sicher. Aber für n=40n = 40 ist 402+40+41=1681=41⋅4140^2 + 40 + 41 = 1681 = 41 \cdot 41, keine Primzahl.

Man braucht also ein Beweisverfahren für Aussagen der Form "für alle natürlichen Zahlen nn gilt ...". Die Idee ist die einer Reihe von Dominosteinen: Wenn der erste fällt und jeder fallende Stein seinen Nachfolger umwirft, dann fallen alle. Das ist die vollständige Induktion. In der vorigen Lektion haben wir die Bernoulli-Ungleichung genau aus diesem Grund unbewiesen gelassen; hier holen wir den Beweis nach.

Vermute zuerst

Du hast nachgerechnet, dass n2+n+41n^2 + n + 41 für n=0,1,…,10n = 0, 1, \dots, 10 eine Primzahl ist. Was folgt daraus?

Definition

Schreibweisen: natürliche Zahlen, Summen, Potenzen

Wir schreiben N={1,2,3,… }\mathbb{N} = \{1, 2, 3, \dots\} und N0={0,1,2,… }\mathbb{N}_0 = \{0, 1, 2, \dots\}. Eine Aussageform A(n)A(n) ist ein Prädikat wie in der Prädikatenlogik: Für jede eingesetzte Zahl nn entsteht eine Aussage, die wahr oder falsch ist.

Das Summenzeichen kürzt lange Summen ab. Für Zahlen a1,a2,…,ana_1, a_2, \dots, a_n ist

∑k=1nak=a1+a2+⋯+an.\sum_{k=1}^{n} a_k = a_1 + a_2 + \dots + a_n.

Der Buchstabe kk heißt Laufindex; er läuft von der unteren Grenze 11 bis zur oberen Grenze nn, sein Name ist beliebig. Genau genommen ist die Summe rekursiv definiert, das heißt Schritt für Schritt aus dem vorigen Wert: ∑k=11ak=a1\sum_{k=1}^{1} a_k = a_1 und ∑k=1n+1ak=∑k=1nak+an+1\sum_{k=1}^{n+1} a_k = \sum_{k=1}^{n} a_k + a_{n+1}. Ebenso die Potenzen: a0=1a^0 = 1 und an+1=an⋅aa^{n+1} = a^n \cdot a.

Beispiel: ∑k=14k2=1+4+9+16=30\sum_{k=1}^{4} k^2 = 1 + 4 + 9 + 16 = 30.

Kurz geprüft

Berechne ∑k=15(2k−1)\sum_{k=1}^{5} (2k - 1).

Satz

Prinzip der vollständigen Induktion

Es sei n0∈N0n_0 \in \mathbb{N}_0 und A(n)A(n) eine Aussageform für ganze Zahlen n≥n0n \geq n_0. Es gelte:

  • Induktionsanfang: A(n0)A(n_0) ist wahr.
  • Induktionsschritt: Für jedes n≥n0n \geq n_0 gilt: Wenn A(n)A(n) wahr ist, dann ist auch A(n+1)A(n + 1) wahr.

Dann ist A(n)A(n) für alle n≥n0n \geq n_0 wahr. Die Annahme "A(n)A(n) ist wahr" im Schritt heißt Induktionsvoraussetzung, die zu zeigende Aussage A(n+1)A(n + 1) Induktionsbehauptung.

Schritt für Schritt

Die gaußsche Summenformel

Behauptung: Für alle n∈Nn \in \mathbb{N} gilt A(n)A(n): ∑k=1nk=n(n+1)2\sum_{k=1}^{n} k = \frac{n(n+1)}{2}.

  1. Induktionsanfang n=1n = 1: Links steht ∑k=11k=1\sum_{k=1}^{1} k = 1, rechts 1⋅22=1\frac{1 \cdot 2}{2} = 1.

Schritt 1 von 4
Kurz geprüft

Für die Formel ∑k=1n(2k−1)=n2\sum_{k=1}^{n} (2k - 1) = n^2 aus der Einleitung lautet der Induktionsschritt ∑k=1n+1(2k−1)=n2+(… )\sum_{k=1}^{n+1} (2k - 1) = n^2 + (\dots). Welcher Term gehört in die Klammer? Schreibe ihn in nn.

Potenzen mit ^, Wurzel als sqrt(x), Brüche mit / und Klammern.

Satz

Bernoulli-Ungleichung

Für alle reellen Zahlen x≥−1x \geq -1 und alle n∈Nn \in \mathbb{N} gilt

(1+x)n≥1+nx(1 + x)^n \geq 1 + nx
Beispiel

Ein späterer Induktionsanfang: 2 hoch n gegen n Quadrat

Vergleiche 2n2^n und n2n^2:

nn11223344556677
2n2^n224488161632326464128128
n2n^21144991616252536364949

Die Behauptung "2n>n22^n > n^2" ist für n=2,3,4n = 2, 3, 4 falsch. Wir beweisen sie für alle n≥5n \geq 5, also mit n0=5n_0 = 5.

Induktionsanfang n=5n = 5: 32>2532 > 25.

Induktionsschritt: Es gelte 2n>n22^n > n^2 für ein n≥5n \geq 5. Dann ist

2n+1=2⋅2n>2n2=n2+n⋅n≥n2+5n=n2+2n+3n>n2+2n+1=(n+1)22^{n+1} = 2 \cdot 2^n > 2n^2 = n^2 + n \cdot n \geq n^2 + 5n = n^2 + 2n + 3n > n^2 + 2n + 1 = (n + 1)^2

Benutzt werden die Induktionsvoraussetzung, n≥5n \geq 5 (für n⋅n≥5nn \cdot n \geq 5n) und 3n>13n > 1. Mit einer feineren Abschätzung ginge der Schritt schon ab n=3n = 3. Trotzdem ist die Aussage für n=3n = 3 und n=4n = 4 falsch, denn dort fehlt ein wahrer Anfang. Erst Anfang und Schritt zusammen, mit demselben n0n_0, ergeben einen Beweis.

Beispiel

Teilbarkeit

Für ganze Zahlen a,ba, b heißt aa ein Teiler von bb, geschrieben a∣ba \mid b, wenn es ein k∈Zk \in \mathbb{Z} gibt mit b=kab = ka.

Behauptung: Für alle n∈N0n \in \mathbb{N}_0 gilt 3∣4n−13 \mid 4^n - 1.

Induktionsanfang n=0n = 0: 40−1=0=3⋅04^0 - 1 = 0 = 3 \cdot 0.

Induktionsschritt: Es gelte 4n−1=3k4^n - 1 = 3k mit k∈Zk \in \mathbb{Z}. Der Trick ist, den Ausdruck für n+1n + 1 so umzuformen, dass 4n−14^n - 1 darin vorkommt:

4n+1−1=4⋅4n−4+3=4(4n−1)+3=4⋅3k+3=3(4k+1)4^{n+1} - 1 = 4 \cdot 4^n - 4 + 3 = 4(4^n - 1) + 3 = 4 \cdot 3k + 3 = 3(4k + 1)

Also ist 3∣4n+1−13 \mid 4^{n+1} - 1. Probe: 43−1=63=3⋅214^3 - 1 = 63 = 3 \cdot 21.

Beispiel

Eine Rekursion auflösen

Eine Folge sei rekursiv definiert durch a1=1a_1 = 1 und an+1=2an+1a_{n+1} = 2a_n + 1 für n∈Nn \in \mathbb{N}. (So viele Züge braucht man mindestens beim Spiel "Türme von Hanoi" mit nn Scheiben.) Die ersten Glieder sind 1,3,7,15,311, 3, 7, 15, 31. Das sind immer Zweierpotenzen minus eins.

Vermutung: an=2n−1a_n = 2^n - 1 für alle n∈Nn \in \mathbb{N}.

Induktionsanfang: a1=1=21−1a_1 = 1 = 2^1 - 1.

Induktionsschritt: Es gelte an=2n−1a_n = 2^n - 1. Dann ist

an+1=2an+1=2(2n−1)+1=2n+1−1a_{n+1} = 2a_n + 1 = 2(2^n - 1) + 1 = 2^{n+1} - 1

Rekursion und Induktion passen zusammen: Die Rekursion sagt, wie an+1a_{n+1} aus ana_n entsteht, und genau diesen Zusammenhang benutzt der Induktionsschritt. Die Vermutung selbst kommt aus den ersten Gliedern; die Induktion macht aus ihr einen Satz.

Satz

Starke Induktion

Es sei n0∈N0n_0 \in \mathbb{N}_0 und A(n)A(n) eine Aussageform. Es gelte A(n0)A(n_0), und für jedes n≥n0n \geq n_0 gelte: Wenn A(k)A(k) für alle kk mit n0≤k≤nn_0 \leq k \leq n wahr ist, dann ist A(n+1)A(n + 1) wahr. Dann ist A(n)A(n) für alle n≥n0n \geq n_0 wahr.

Der Unterschied: Im Schritt darf man nicht nur den direkten Vorgänger benutzen, sondern alle früheren Fälle.

Beispiel

Jede Zahl ab 2 ist ein Produkt von Primzahlen

Behauptung: Jedes n≥2n \geq 2 ist eine Primzahl oder ein Produkt von Primzahlen.

Induktionsanfang n=2n = 2: 22 ist eine Primzahl.

Induktionsschritt: Die Behauptung gelte für alle kk mit 2≤k≤n2 \leq k \leq n. Ist n+1n + 1 eine Primzahl, sind wir fertig. Sonst gibt es eine Zerlegung n+1=abn + 1 = ab mit ganzen Zahlen 2≤a≤n2 \leq a \leq n und 2≤b≤n2 \leq b \leq n. Nach Voraussetzung sind aa und bb Primzahlen oder Produkte von Primzahlen, also auch n+1=abn + 1 = ab.

Hier hilft die gewöhnliche Induktion nicht: Die Faktoren von n+1n + 1 sind kleiner als n+1n + 1, aber im Allgemeinen nicht gleich nn. Zum Beispiel ist 12=3⋅412 = 3 \cdot 4, und über 1111 zu wissen hilft dabei nichts.

Häufige Fehler

Den Induktionsanfang vergessen

"Behauptung: ∑k=1nk=n(n+1)2+1\sum_{k=1}^{n} k = \frac{n(n+1)}{2} + 1. Schritt: Gilt das für nn, dann ist ∑k=1n+1k=n(n+1)2+1+(n+1)=(n+1)(n+2)2+1\sum_{k=1}^{n+1} k = \frac{n(n+1)}{2} + 1 + (n + 1) = \frac{(n+1)(n+2)}{2} + 1. Also gilt es für alle nn."

Richtig ist

Der Schritt ist korrekt gerechnet, und trotzdem ist die Formel für jedes nn falsch: Für n=1n = 1 steht links 11 und rechts 22. Der Schritt zeigt nur "wenn es für nn gilt, dann für n+1n + 1". Ohne einen wahren Startfall fällt kein einziger Dominostein. Prüfe den Induktionsanfang immer zuerst, und prüfe ihn wirklich durch Einsetzen.

Häufige Fehler

Alle Pferde haben dieselbe Farbe

"Behauptung A(n)A(n): In jeder Menge von nn Pferden haben alle dieselbe Farbe. Anfang n=1n = 1: Ein Pferd hat dieselbe Farbe wie es selbst. Schritt: Gegeben seien n+1n + 1 Pferde P1,…,Pn+1P_1, \dots, P_{n+1}. Ohne Pn+1P_{n+1} bleiben nn Pferde, die nach Voraussetzung gleichfarbig sind; ebenso ohne P1P_1. Die beiden Gruppen überschneiden sich, also haben alle n+1n + 1 dieselbe Farbe."

Richtig ist

Der Schritt muss für jedes n≥n0n \geq n_0 funktionieren, und für n=1n = 1 tut er das nicht. Bei zwei Pferden sind die beiden Gruppen {P1}\{P_1\} und {P2}\{P_2\}. Sie überschneiden sich nicht, und es gibt kein Pferd, über das man die Farben vergleichen könnte. Der Schritt von 11 auf 22 ist also falsch; alle anderen Schritte (ab n=2n = 2) sind zwar richtig, aber sie hängen an diesem einen. Prüfe den Schritt besonders für das kleinste nn, bei dem er benutzt wird.

Zusammenfassung

  • Vollständige Induktion: Aus dem Induktionsanfang A(n0)A(n_0) und dem Induktionsschritt "A(n)⇒A(n+1)A(n) \Rightarrow A(n+1) für jedes n≥n0n \geq n_0" folgt A(n)A(n) für alle n≥n0n \geq n_0.

  • Das Prinzip folgt aus dem Wohlordnungsprinzip: Ein kleinstes Gegenbeispiel kann es nicht geben.

  • Summen und Potenzen sind rekursiv definiert. Im Schritt spaltet man den letzten Summanden oder Faktor ab und setzt die Induktionsvoraussetzung ein.

  • Bei Ungleichungen schätzt man im Schritt geschickt ab; bei Teilbarkeit formt man so um, dass der Ausdruck für nn wieder auftaucht.

  • Der Induktionsanfang darf bei jedem n0n_0 liegen, er muss aber zum Schritt passen (2n>n22^n > n^2 erst ab n=5n = 5).

  • Starke Induktion erlaubt im Schritt alle früheren Fälle; sie folgt aus der gewöhnlichen Induktion.

  • Typische Fehler: Induktionsanfang vergessen und ein Schritt, der für das kleinste nn nicht funktioniert (Pferde).

Übungen

Aufgabe 1Numerisch

Berechne ∑k=120k\sum_{k=1}^{20} k mit der gaußschen Summenformel.

Aufgabe 2Multiple Choice

Jemand "beweist" n=n+1n = n + 1 für alle n∈Nn \in \mathbb{N} so: Gilt n=n+1n = n + 1, dann folgt durch Addieren von 11 auf beiden Seiten n+1=n+2n + 1 = n + 2. Was ist falsch?

Aufgabe 3Term eingeben

Die Folge sei definiert durch a0=0a_0 = 0 und an+1=3an+2a_{n+1} = 3a_n + 2 für n∈N0n \in \mathbb{N}_0. Berechne die ersten Glieder, stelle eine geschlossene Formel für ana_n auf und prüfe sie mit Induktion.

Potenzen mit ^, Wurzel als sqrt(x), Brüche mit / und Klammern.

Aufgabe 4Freitext

Beweise mit vollständiger Induktion: Für alle n∈Nn \in \mathbb{N} gilt ∑k=1nk2=n(n+1)(2n+1)6\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}.

Aufgabe 5Freitext

Beweise mit vollständiger Induktion: Für alle n∈Nn \in \mathbb{N} ist n3+2nn^3 + 2n durch 33 teilbar.

Aufgabe 6Numerisch

Für n∈Nn \in \mathbb{N} sei n!=1⋅2⋅…⋅nn! = 1 \cdot 2 \cdot \ldots \cdot n (gelesen "nn Fakultät"). Ab welchem kleinsten n0n_0 gilt n!>2nn! > 2^n für alle n≥n0n \geq n_0?

Aufgabe 7Freitext

Die Fibonacci-Zahlen sind definiert durch F1=F2=1F_1 = F_2 = 1 und Fn+1=Fn+Fn−1F_{n+1} = F_n + F_{n-1} für n≥2n \geq 2. Beweise: Fn<2nF_n < 2^n für alle n∈Nn \in \mathbb{N}. Warum brauchst du zwei Startfälle?