Starke Induktion oder Wertverlaufsinduktion

Wir betrachten nun eine neue Form der Induktion, bei der wir eine stärkere Induktionsvoraussetzung geschenkt bekommen. Dies kann die Argumentation erleichtern. Wir formulieren diese Form wieder in drei äquivalenten Versionen.

Satz (Prinzip der starken Induktion)

Vererbt sich eine Eigenschaft natürlicher Zahlen für jede natürliche Zahl n von allen natürlichen Zahlen k < n auf n, so gilt sie für jede natürliche Zahl.

Satz (Prinzip der starken Induktion, formale Version)

Sei ℰ(n) eine Eigenschaft natürlicher Zahlen. Dann gilt:

∀n (∀k<nℰ(k) → ℰ(n)) → ∀n ℰ(n)

Satz (Prinzip der starken Induktion, Version für Mengen)

Sei A ⊆ ℕ. Dann gilt:

∀n ({ 0, ..., n − 1 } ⊆ A → n  ∈  A) → A = ℕ

Wir können die starke Induktion mit Hilfe der üblichen Induktion beweisen:

Beweis

Wir zeigen die Version für Eigenschaften. Es gelte also

(1) ∀n (∀k<nℰ(k) → ℰ(n)).

Unser Beweisziel ist:

(2) ∀n ℰ(n).

Dieses Ziel erreichen wir durch einen logischen Trick. Wir zeigen nämlich:

(3) ∀n ∀k < n ℰ(k)

Dies genügt. Zum Beweis von (3) verwenden wir die übliche Induktion, und zwar für die neue Eigenschaft

ℰ′(n) = „∀k < n ℰ(k)“.

Diese Eigenschaft besagt anschaulich, dass ℰ „unterhalb von n“ gilt.

Induktionsanfang n = 0:

Hier ist nichts zu zeigen, da es kein k < 0 gibt.

Induktionsschritt von n nach n + 1:

Sei n beliebig und es gelte ℰ′(n), d. h.

∀k < n ℰ(k) (I. V.)

Nun wenden wir unsere Voraussetzung (1) an und schließen auf ℰ(n). Dann gilt also

∀k < n ℰ(k) ∧ ℰ(n),

sodass

∀k < n + 1 ℰ(k).

Die starke Induktion kann erneut schematisch angewendet werden:

Verlauf eines Beweises durch starke Induktion

Um zu zeigen, dass jede natürliche Zahl n die Eigenschaft ℰ besitzt, können wir so vorgehen:

Induktionsschritt n:

Wir zeigen ℰ(n) mit Hilfe der (starken) Induktionsvoraussetzung

„ℰ(k) für alle k < n“. Hierbei ist n eine beliebige natürliche Zahl.

Ein Induktionsanfang entfällt bei der starken Induktion. Für n = 0 ist die Induktionsvoraussetzung leer, da es keine natürliche Zahl k kleiner als 0 gibt. Der Fall n = 0 wird also im allgemeinen Induktionsschritt n automatisch mit erfasst. Dennoch kann es bei der Durchführung der starken Induktion hilfreich sein, vorab ℰ(0) zu zeigen (oder auch mehrere Einzelfälle ℰ(0), …, ℰ(n₀)). Wir können dann für den Induktionsschritt n ≥ 1 (bzw. n > n₀) annehmen. Alternativ ist im Induktionsschritt wie in jedem Beweis natürlich auch eine Fallunterscheidung möglich.

Wie für die einfache Induktion lässt sich die starke Induktion auch ab einer Stelle oder für eine gewisse (endliche oder unendliche) Menge von natürlichen Zahlen durchführen.