Die vollständige Induktion

Definition

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

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

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

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

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

Induktionsschritt. Die Formel gelte im Rang $n$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}$1+2+⋯+n+(n+1)=2n(n+1)​+(n+1)=2n(n+1)+2(n+1)​=2(n+1)(n+2)​

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

Beide Schritte sind nötig

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

Diese Eigenschaft ist erblich: gilt $n = n+1$n=n+1, so ergibt die Addition von 1 auf beiden Seiten $n + 1 = n + 2$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

Manche Beweise verlangen mehr als den Vorgängerrang. Die starke Induktion setzt $P(k)$P(k) für alle $k \leq n$k≤n voraus, nicht nur für $n$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.