Die Induktion beweist unendlich viele Aussagen mit zwei Prüfungen: einem Anfangspunkt und einem Schritt, der sich fortpflanzt.

Die vollständige Induktion

Definition FAKT

Die Induktion beweist, dass eine Eigenschaft $P(n)$ für jede ganze Zahl ab einem Rang $n_0$ gilt, und zwar mit nur zwei Prüfungen:

Schritt	Was gezeigt wird
Induktionsanfang	$P(n_0)$ ist wahr
Induktionsschritt	Ist $P(n)$ wahr, so auch $P(n+1)$

Diese beiden Punkte begründen unendlich viele Aussagen. Darin liegt ihre Kraft: geprüft wird stets nur ein Fall und eine Implikation.

Ein Bild und seine Grenze ANALOGIE

Eine Reihe von Dominosteinen: den ersten umzustoßen und zu gewährleisten, dass jeder den nächsten umwirft, genügt, um alle fallen zu lassen.

Das Bild trifft den Mechanismus und verfehlt die Reichweite. Eine Dominoreihe ist endlich und das Fallen braucht Zeit; die Induktion betrifft unendlich viele Ränge und läuft nicht ab. Sie erzählt keine Ausbreitung, sie beweist eine Eigenschaft.

Ein zu Ende geführtes Beispiel FAKT

Zeigen wir, dass die Summe der ersten $n$ ganzen Zahlen $\dfrac{n(n+1)}{2}$ beträgt.

Induktionsanfang. Für $n = 1$ : die Summe ist 1, und $\dfrac{1 \times 2}{2} = 1$ .

Induktionsschritt. Die Formel gelte im Rang $n$ . Dann:

$1 + 2 + \dots + n + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$

Das ist die Formel im Rang $n+1$ . Beide Schritte halten, also gilt die Eigenschaft für jedes $n \geq 1$ .

Beide Schritte sind nötig FAKT

Der Induktionsschritt allein beweist nichts. Nehmen wir $P(n)$ : „ $n = n + 1$ ".

Diese Eigenschaft ist erblich: gilt $n = n+1$ , so ergibt die Addition von 1 auf beiden Seiten $n + 1 = n + 2$ . Der Schritt pflanzt sich einwandfrei fort — und die Eigenschaft ist für jede ganze Zahl falsch, weil kein Rang sie in Gang setzt.

Der Anfang allein genügt ebenso wenig: eine Eigenschaft kann bei 1 wahr und danach falsch sein.

Starke Induktion FAKT

Manche Beweise verlangen mehr als den Vorgängerrang. Die starke Induktion setzt $P(k)$ für alle $k \leq n$ voraus, nicht nur für $n$ .

Sie dient, wenn der Schritt auf einen weit früheren Rang zurückgreift — die Zerlegung einer ganzen Zahl in Primfaktoren etwa verweist auf zwei beliebige kleinere Faktoren, nicht auf den Vorgänger.

Zusammenfassung

Ein Anfangspunkt und ein sich fortpflanzender Schritt beweisen unendlich viele Fälle; auf keinen von beiden lässt sich verzichten.