Vollständige Induktion

Grundidee und Bedeutung

Die vollständige Induktion ist eine mathematische Beweismethode, mit der eine von einer natürlichen Zahl n abhängige Aussage A(n) für alle natürlichen Zahlen bewiesen wird. Sie ist nötig, weil unendlich viele Fälle nicht einzeln überprüft werden können. Obwohl die Bezeichnung „Induktion“ lautet, handelt es sich um ein deduktives Verfahren: Aus festgelegten Voraussetzungen wird die Behauptung logisch hergeleitet.

Ein Induktionsbeweis besteht aus zwei Teilen:

• Induktionsanfang oder Induktionsverankerung: Man beweist A(0), A(1) oder einen anderen vorgesehenen Startfall.
• Induktionsschritt oder Induktionsschluss: Für ein beliebiges n nimmt man A(n) als Induktionsannahme beziehungsweise Induktionsvoraussetzung an und zeigt daraus die Induktionsbehauptung A(n+1). Formal beweist man also A(n) ⇒ A(n+1).

Dabei wird im Induktionsschritt kein bestimmter Zahlenwert für n eingesetzt. Außerdem wird A(n) an dieser Stelle nicht erneut bewiesen, sondern vorübergehend vorausgesetzt, um die Folgerung für den Nachfolger herzuleiten.

Anschaulich entspricht das Verfahren einer unendlichen Reihe von Dominosteinen: Der Induktionsanfang sorgt dafür, dass der erste Stein fällt. Der Induktionsschritt stellt sicher, dass jeder fallende Stein den nächsten umstößt. Zusammen folgt daraus, dass jeder Stein der Reihe irgendwann fällt.

Vollständige Induktion ist nicht auf arithmetische Formeln beschränkt. Sie kann allgemein verwendet werden, wenn Aussagen nummeriert werden können, von natürlichen Zahlen abhängen und zwischen aufeinanderfolgenden Fällen ein geeigneter inhaltlicher Zusammenhang besteht. Deshalb ist sie in vielen Gebieten der Mathematik grundlegend.

Induktionsprinzip und logische Grundlage

Das Prinzip der vollständigen Induktion lautet: Ist A(n) eine Aussage über natürliche Zahlen, gilt A(0) beziehungsweise A(1), und zieht für alle n die Gültigkeit von A(n) die Gültigkeit von A(n+1) nach sich, dann gilt A(n) für jede natürliche Zahl.

Als formale Schlussregel mit dem Ableitungsoperator ⊢ kann es geschrieben werden als

A(0) ∧ ∀n ∈ ℕ: (A(n) ⇒ A(n+1)) ⊢ ∀n ∈ ℕ: A(n).

Das Induktionsprinzip kann als Axiom gesetzt oder aus anderen Axiomen hergeleitet werden. In Arithmetik und Zahlentheorie wird es meist aus dem gleichwertigen fünften Peano-Axiom, dem Induktionsaxiom, gewonnen. Dieses besagt: Ist K eine Teilmenge von ℕ, enthält K die Zahl 1 und gehört mit jedem n ∈ K auch n+1 zu K, dann ist K = ℕ.

Das Prinzip ist auch in anderen Konstruktionen der natürlichen Zahlen herleitbar, etwa wenn ℕ als von 1 erzeugte geordnete Halbgruppe, als frei von 1 erzeugtes Monoid, als Algebra mit Nachfolger-Abbildung, als kleinste induktive Menge oder als Klasse der endlichen Ordinalzahlen aufgefasst wird.

Typische Beweise

Ein Standardbeispiel ist die Gaußsche Summenformel. Für alle natürlichen Zahlen n ≥ 1 gilt

1 + 2 + ⋯ + n = n(n+1)/2.

Der Induktionsanfang n = 1 folgt aus 1 = 1(1+1)/2. Für den Induktionsschritt wird

1 + 2 + ⋯ + n = n(n+1)/2

angenommen. Dann gilt

1 + 2 + ⋯ + n + (n+1) = n(n+1)/2 + (n+1) = [n(n+1) + 2(n+1)]/2 = (n+1)(n+2)/2 = (n+1)((n+1)+1)/2.

Damit folgt die Formel für n+1 und nach dem Induktionsprinzip für alle n ≥ 1.

Ein weiteres Beispiel ist die bernoullische Ungleichung. Für alle reellen Zahlen x ≥ −1 und alle natürlichen Zahlen n ≥ 0 gilt

(1+x)^n ≥ 1+nx.

Für n = 0 ist (1+x)^0 = 1 ≥ 1. Unter der Induktionsannahme (1+x)^n ≥ 1+nx erhält man

(1+x)^(n+1) = (1+x)^n(1+x) ≥ (1+nx)(1+x) = 1+x+nx+nx² ≥ 1+x+nx = 1+(n+1)x.

Die Voraussetzung x ≥ −1 gewährleistet, dass 1+x nicht negativ ist; außerdem ist nx² ≥ 0. Somit gilt die Ungleichung für alle n ∈ ℕ₀.

Auch geometrische Aussagen lassen sich so beweisen: Jede beliebige Anzahl von Geraden zerlegt die Ebene in Teilflächen, die mit zwei Farben so gefärbt werden können, dass angrenzende Flächen verschiedene Farben haben. Fügt man zu einer zulässig gefärbten Anordnung aus n Geraden eine weitere Gerade hinzu, lässt man die Farben in einer der beiden neuen Halbebenen unverändert und vertauscht sie in der anderen. Dadurch entsteht wieder eine zulässige Färbung.

Varianten der Induktion

Bei der Induktion mit beliebigem Anfang soll A(n) erst für n ≥ n₀ bewiesen werden. Dann zeigt man A(n₀) und anschließend für jedes n ≥ n₀ den Schluss A(n) ⇒ A(n+1). Nicht erfasste kleinere Werte müssen getrennt untersucht werden. Beispielsweise gilt 2^n ≥ n² für n ≥ 4: Der Anfang ist 2⁴ = 16 ≥ 16 = 4². Aus 2^n ≥ n² und n ≥ 4 folgt

2^(n+1) = 2·2^n ≥ 2n² = n²+n·n ≥ n²+4n ≥ n²+2n+1 = (n+1)².

Für n = 3 ist die Ungleichung dagegen falsch.

Bei einer Induktion mit mehreren Vorgängern verwendet der Schritt mehrere frühere Aussagen. Benötigt man beispielsweise A(n) und A(n−1), müssen zwei aufeinanderfolgende Startfälle, etwa 0 und 1, bewiesen werden.

Die starke Induktion nimmt für ein beliebiges k alle früheren Aussagen A(1), A(2), …, A(k−1) an und leitet daraus A(k) her. Sie ist zur gewöhnlichen Induktion logisch äquivalent, erlaubt aber den direkten Rückgriff auf beliebig viele Vorgänger. So lässt sich zeigen, dass jede natürliche Zahl n ≥ 2 einen Primzahl-Teiler besitzt: Ist n+1 prim, teilt es sich selbst. Ist n+1 = a·b mit 1 < a < n+1, besitzt a nach der starken Induktionsvoraussetzung einen Primzahl-Teiler p; dieser teilt dann auch n+1.

Bei der Induktion mit Vorwärts-Rückwärts-Schritten werden zunächst Sprünge, etwa von 2^k nach 2^(k+1), bewiesen und anschließend die Lücken durch rückwärts gerichtete Schlüsse von 2^k zu n < 2^k geschlossen. Diese Variante verwendete Augustin-Louis Cauchy 1821 für die Ungleichung vom arithmetischen und geometrischen Mittel.

Für Aussagen über alle ganzen Zahlen kann man vom Anfangswert sowohl den Schritt n → n+1 als auch, wenn möglich, n → n−1 durchführen. Weitere Verallgemeinerungen sind die transfinite Induktion für Ordinalzahlen und die strukturelle Induktion auf fundierten Mengen mit einer geeigneten Ordnungsstruktur.

Fehlerquelle und rekursive Definition

Das Pferde-Paradox zeigt eine typische fehlerhafte Anwendung. Angeblich wird bewiesen, dass in jeder Herde von n Pferden alle Pferde dieselbe Farbe haben. Der verwendete Induktionsschritt würde jedoch eine Verankerung bei einem n ≥ 2 benötigen, während der scheinbare Beweis bei n = 1 beginnt. Deshalb scheitert bereits der Übergang von n = 1 zu n = 2. Ein gültiger Induktionsbeweis verlangt also, dass der Induktionsschritt tatsächlich unmittelbar an die bewiesenen Anfangsfälle anschließt.

Mit der vollständigen Induktion verwandt ist die rekursive oder induktive Definition. Dabei wird kein Satz bewiesen, sondern ein mathematischer Ausdruck durch einen Rekursionsanfang und einen Rekursionsschritt für alle natürlichen Zahlen festgelegt. Beispielsweise werden die Potenzen einer Zahl x definiert durch

x¹ := x

und

x^(n+1) := x^n·x.

Der Anfang bestimmt den ersten Wert; die Rekursionsformel erzeugt aus jedem bereits definierten Wert den folgenden.