Vollständige Induktion
Wie beweist man, dass eine Formel für alle natürlichen Zahlen gilt – also unendlich viele Fälle? Ausprobieren reicht nicht. Die vollständige Induktion ist das Beweisverfahren dafür, und sie gehört im ersten Semester fast jedes Mathe-, Informatik- und Ingenieurstudiums zum Standard.
Die Idee: Dominosteine
Stell Dir eine unendlich lange Reihe von Dominosteinen vor. Damit alle umfallen, brauchst Du zwei Dinge:
- Der erste Stein fällt um.
- Jeder Stein, der umfällt, stößt den nächsten um.
Genau so funktioniert die Induktion. $A(n)$ ist eine Aussage, die von einer natürlichen Zahl $n$ abhängt, zum Beispiel „$1 + 2 + \ldots + n = \frac{n(n+1)}{2}$“.
Prinzip der vollständigen Induktion
Es sei $n_0$ eine natürliche Zahl. Wenn
- $A(n_0)$ wahr ist (Induktionsanfang) und
- für jedes $n \ge n_0$ aus der Gültigkeit von $A(n)$ die Gültigkeit von $A(n+1)$ folgt (Induktionsschritt),
dann ist $A(n)$ für alle natürlichen Zahlen $n \ge n_0$ wahr.
Das Schema
So schreibst Du einen Induktionsbeweis auf – in Klausuren wird genau diese Gliederung erwartet:
| Teil | Was Du tust |
|---|---|
| Induktionsanfang (IA) | Du setzt den Startwert $n_0$ ein (meist $n_0 = 1$) und rechnest nach, dass $A(n_0)$ stimmt. |
| Induktionsvoraussetzung (IV) | „Für ein festes, aber beliebiges $n \ge n_0$ gelte $A(n)$.“ |
| Induktionsbehauptung (IB) | Du schreibst auf, was zu zeigen ist: $A(n+1)$ – also die Aussage, in der überall $n + 1$ statt $n$ steht. |
| Induktionsschritt (IS) | Du beweist $A(n+1)$ und benutzt dabei die Voraussetzung $A(n)$. Markiere die Stelle, an der Du die IV einsetzt. |
Achtung bei der Induktionsvoraussetzung
Die Voraussetzung lautet nicht „$A(n)$ gilt für alle $n$“ – das wäre ja schon die Behauptung, und der Beweis würde sich im Kreis drehen. Du setzt nur voraus, dass $A(n)$ für ein bestimmtes $n$ gilt, und zeigst, dass es dann auch für den Nachfolger $n + 1$ gilt. Weil $n$ beliebig war, gilt dieser Schluss für jedes $n$.
Beispiel 1: eine Summenformel
Behauptung: Für alle $n \in \mathbb{N}$ gilt $\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$.
IA ($n = 1$): Links steht $\sum_{k=1}^{1} k = 1$, rechts $\frac{1 \cdot 2}{2} = 1$. Die Aussage stimmt.
IV: Für ein festes $n \in \mathbb{N}$ gelte $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$.
IB: Dann gilt auch $\sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2}$.
IS: Spalte den letzten Summanden ab und setze die IV ein:
Das ist genau die Induktionsbehauptung. Damit ist die Formel für alle $n \in \mathbb{N}$ bewiesen. $\square$
Tipp
Bei Summen beginnt der Induktionsschritt fast immer gleich: letzten Summanden abspalten, IV einsetzen, zusammenfassen. Weißt Du nicht, wie Du zusammenfassen sollst, schau auf das Ziel – hier hilft es, $(n+1)$ auszuklammern. Mehr zu Summen: Summenzeichen.
Beispiel 2: Teilbarkeit
Behauptung: Für alle $n \in \mathbb{N}$ ist $n^3 + 2n$ durch 3 teilbar.
IA ($n = 1$): $1^3 + 2 \cdot 1 = 3$ ist durch 3 teilbar.
IV: Für ein festes $n \in \mathbb{N}$ sei $n^3 + 2n$ durch 3 teilbar, also $n^3 + 2n = 3m$ mit einer ganzen Zahl $m$.
IB: Dann ist auch $(n+1)^3 + 2(n+1)$ durch 3 teilbar.
IS: Multipliziere aus und suche den Term aus der IV:
Weil $m + n^2 + n + 1$ eine ganze Zahl ist, ist der Ausdruck durch 3 teilbar. $\square$
Beispiel 3: eine Ungleichung mit späterem Start
Behauptung: Für alle natürlichen Zahlen $n \ge 5$ gilt $2^n \gt n^2$.
Probiere zuerst kleine Zahlen: Für $n = 1$ stimmt es ($2 \gt 1$), für $n = 2, 3, 4$ aber nicht ($4 \gt 4$, $8 \gt 9$ und $16 \gt 16$ sind falsch). Erst ab $n = 5$ gilt die Ungleichung durchgehend – deshalb ist $n_0 = 5$.
IA ($n = 5$): $2^5 = 32 \gt 25 = 5^2$.
IV: Für ein festes $n \ge 5$ gelte $2^n \gt n^2$.
IB: Dann gilt $2^{n+1} \gt (n+1)^2$.
IS:
Dabei wurde zweimal $n \ge 5$ benutzt: $n^2 = n \cdot n \ge 5n$ und $5n = 2n + 3n \gt 2n + 1$. $\square$
Tipp für Ungleichungen
Schreib Dir das Ziel $(n+1)^2$ an den Rand und schätze von $2^{n+1}$ aus nur in eine Richtung ab (hier immer „größer“). Jede Abschätzung muss für alle $n \ge n_0$ stimmen.
Typische Fehler
Häufige Fehler – und warum sie den Beweis ungültig machen
- Induktionsanfang vergessen. Für die falsche Aussage „$n + 1 \lt n$ für alle $n$“ funktioniert der Induktionsschritt sogar: Aus $n + 1 \lt n$ folgt durch Addition von 1 $n + 2 \lt n + 1$. Trotzdem ist die Aussage für kein $n$ wahr – der erste Dominostein fällt nicht.
- Voraussetzung „für alle $n$“. Damit setzt Du voraus, was Du beweisen willst (Zirkelschluss).
- IV im Schritt nicht benutzt. Dann ist es kein Induktionsbeweis – und meistens ist irgendwo ein Fehler.
- Von der Behauptung aus rückwärts rechnen und am Ende „$0 = 0$“ erhalten. Das ist nur dann ein Beweis, wenn jeder Schritt eine Äquivalenzumformung ist. Sicherer: von der linken Seite der IB zur rechten Seite umformen.
- Falscher Startwert. Der Induktionsanfang muss genau bei dem $n_0$ gemacht werden, ab dem die Aussage gelten soll – und der Induktionsschritt muss für alle $n \ge n_0$ funktionieren.
Varianten
- Induktion ab $n_0$: wie in Beispiel 3 – der Anfang ist nicht immer bei 1 (oft auch bei 0).
- Starke Induktion: Im Schritt darfst Du voraussetzen, dass $A(k)$ für alle $k$ von $n_0$ bis $n$ gilt. Das braucht man zum Beispiel, um zu zeigen, dass jede Zahl $n \ge 2$ ein Produkt von Primzahlen ist.
Online üben
Die Aufgaben trainieren die rechnerischen Teile eines Induktionsbeweises: den neuen Summanden finden (Stufe 1), den Induktionsschritt zusammenfassen (Stufe 2) und den richtigen Startwert bestimmen (Stufe 3). Terme gibst Du mit n ein, zum Beispiel (n+1)^2.
Stufe 3: Startwert bei Ungleichungen
-
Aufgabe 1
\(\text{Ab welchem } n_0 \text{ gilt } 2^{n} > 10n\text{ für alle } n \geq n_0\text{?}\)\(n_0 =\)\(n_0 = 6\quad(n = 5:\ 32 > 50\text{ falsch};\ n = 6:\ 64 > 60)\)
-
Aufgabe 2
\(\text{Ab welchem } n_0 \text{ gilt } n! > 3^{n}\text{ für alle } n \geq n_0\text{?}\)\(n_0 =\)\(n_0 = 7\quad(n = 6:\ 720 > 729\text{ falsch};\ n = 7:\ 5040 > 2187)\)
-
Aufgabe 3
\(\text{Ab welchem } n_0 \text{ gilt } n^{2} > 4n + 5\text{ für alle } n \geq n_0\text{?}\)\(n_0 =\)\(n_0 = 6\quad(n = 5:\ 25 > 25\text{ falsch};\ n = 6:\ 36 > 29)\)
-
Aufgabe 4
\(\text{Ab welchem } n_0 \text{ gilt } 2^{n} > n + 10\text{ für alle } n \geq n_0\text{?}\)\(n_0 =\)\(n_0 = 4\quad(n = 3:\ 8 > 13\text{ falsch};\ n = 4:\ 16 > 14)\)
-
Aufgabe 5
\(\text{Ab welchem } n_0 \text{ gilt } n! > n^{2}\text{ für alle } n \geq n_0\text{?}\)\(n_0 =\)\(n_0 = 4\quad(n = 3:\ 6 > 9\text{ falsch};\ n = 4:\ 24 > 16)\)
Tippe Deine Lösung ein und klicke auf „Prüfen“ (oder drücke Enter). Brüche als 3/4, Dezimalzahlen mit Komma, mehrere Lösungen mit ; trennen, Potenzen als x^2, Wurzeln als sqrt(5). Punkte: 10 für richtig beim ersten Versuch, 6 nach einem Fehlversuch, 5 mit Tipp, 0 wenn Du Dir vorher die Lösung anschaust. Deine Punkte und Abzeichen siehst Du unter Mein Training.
Arbeitsblatt: Vollständige Induktion
Bis zu 10 Aufgaben mit Lösungsblatt zum Ausdrucken – bei jedem Klick neue Aufgaben. Klasse 13.
Zurück zum Brückenkurs „Fit fürs Studium“.
Weiterlesen: Vollständige Induktion bei Wikipedia