Vollständige Induktion

Studium

\bigl(A(n_0) \wedge \forall n \geq n_0 : A(n) \Rightarrow A(n+1)\bigr) \;\Rightarrow\; \forall n \geq n_0 : A(n)

Voraussetzung: $n, n_0 \in \mathbb{Z},$ $A(n)$ $Aussage für jedes ganze$ $n \geq n_0$

$A(n)$: Aussage, die von der ganzen Zahl n abhängt
$n_0$: Startwert, ab dem die Aussage gelten soll (meist 0 oder 1)
$A(n_0)$: Induktionsanfang, die Aussage für den Startwert
$A(n) \Rightarrow A(n+1)$: Induktionsschritt, aus der Gültigkeit für n folgt die für n+1

Gilt eine Aussage für einen Startwert und folgt sie stets von n auf n+1, dann gilt sie für alle n ab dem Startwert.

Erklärung

Die vollständige Induktion ist ein Beweisverfahren für Aussagen, die für alle ganzen Zahlen ab einem Startwert $n_0$ gelten sollen. Man zeigt zwei Dinge:

Induktionsanfang: $A(n_0)$ ist wahr.
Induktionsschritt: Für jedes $n \geq n_0$ folgt aus $A(n)$ (der Induktionsvoraussetzung) die Aussage $A(n+1)$ .

Dann gilt $A(n)$ für alle $n \geq n_0$ : Der Anfang liefert $A(n_0)$ , der Schritt liefert daraus $A(n_0 + 1)$ , daraus $A(n_0 + 2)$ und so weiter. Begründet wird das durch das Induktionsaxiom der natürlichen Zahlen, gleichwertig durch die Wohlordnung: Jede nichtleere Menge natürlicher Zahlen hat ein kleinstes Element, also kann es kein kleinstes Gegenbeispiel geben.

Eine Variante ist die starke Induktion: Im Schritt darf man $A(n_0), \ldots, A(n)$ gleichzeitig voraussetzen. Das braucht man etwa bei Rekursionen, die auf zwei Vorgänger zurückgreifen.

Beispiele

Summe der ungeraden Zahlen: Behauptung $1 + 3 + \ldots + (2n-1) = n^2$ für $n \geq 1$ .

Anfang $n = 1$ : links steht $1$ , rechts $1^2 = 1$ .
Schritt: Gilt die Formel für $n$ , so ist

1 + 3 + \ldots + (2n-1) + (2(n+1) - 1) = n^2 + 2n + 1 = (n+1)^2

Probe für $n = 5$ : $1 + 3 + 5 + 7 + 9 = 25 = 5^2$ .

Teilbarkeit: Behauptung $3 \mid n^3 - n$ für alle $n \geq 1$ .

Anfang $n = 1$ : $1 - 1 = 0$ ist durch $3$ teilbar.
Schritt: $(n+1)^3 - (n+1) = (n^3 - n) + 3(n^2 + n)$ . Der erste Summand ist nach Voraussetzung durch $3$ teilbar, der zweite offensichtlich.

Probe: $2^3 - 2 = 6$ und $4^3 - 4 = 60$ sind durch $3$ teilbar.

Typische Fehler

Induktionsanfang weglassen. Für die falsche Aussage „ $2n + 1$ ist gerade“ funktioniert der Schritt: Ist $2n + 1$ gerade, dann auch $2n + 3 = (2n+1) + 2$ . Ohne gültigen Anfang beweist das nichts.
$A(n+1)$ im Schritt schon benutzen. Man muss von der Induktionsvoraussetzung $A(n)$ ausgehen und $A(n+1)$ herleiten, nicht die Behauptung umformen, bis etwas Wahres dasteht.
Schritt nur für ein festes $n$ zeigen. Der Schritt muss für jedes $n \geq n_0$ gelten. Bei Aussagen mit zwei Vorgängern (starke Induktion) braucht man entsprechend zwei Startwerte.
Falscher Startwert. $2^n > n^2$ ist für $n = 2, 3, 4$ falsch (z.B. $2^4 = 16 = 4^2$ ) und gilt dann wieder ab $n = 5$ , denn $2^5 = 32 > 25$ . Der Induktionsbeweis muss deshalb mit $n_0 = 5$ beginnen; der Schritt $2^{n+1} = 2 \cdot 2^n > 2n^2 \geq (n+1)^2$ funktioniert auch erst ab $n \geq 3$ .

Vollständige Induktion