1.11 Die vollständige Induktion

Satz (vollständige Induktion)

Sei ℰ(n) eine Eigenschaft für natürliche Zahlen. Es gelte:

(a)

ℰ(0).

(b)	Für alle n  ∈  ℕ gilt: ℰ(n) impliziert ℰ(n + 1).

Dann gilt ℰ(n) für alle natürlichen Zahlen.

Dieser Satz ist nicht nur in der Zahlentheorie, sondern in der gesamten Mathematik im Einsatz. Obwohl in der Analysis die reellen Zahlen und die komplexen Zahlen im Zentrum stehen, so werden doch häufig auch die natürlichen Zahlen eingesetzt, etwa in Potenzierungen (x + y)ⁿ oder in der Bildung der n-ten Ableitung f ⁽ⁿ⁾ einer Funktion f. Und dann ist die vollständige Induktion oft das Mittel der Wahl, um Aussagen wie zum Beispiel die binomische Formel (x + y)ⁿ = ∑_k ≤ n $( \binom{n}{k} )$ x^k y^n − k oder die Existenz der Ableitungen log⁽ⁿ⁾ des natürlichen Logarithmus log : ] 0, +∞ [ → ℝ für alle n zu beweisen.

Das Wort „Induktion“ steht im Gegensatz zur „Deduktion“, also einer Herleitung, eines Beweises. Induktiv argumentieren bedeutet, dass man von Einzelfällen auf das Allgemeine schließt. Wenn es an den ersten drei Urlaubstagen regnet, sagt man „induktiv“: „Hier regnet es immer, wir fahren wieder weg.“ Und wenn eine Eigenschaft ℰ(n) für alle Zahlen 0, 1, 2, …, 100 gilt, so liegt es nahe, dass sie für alle natürlichen Zahlen gilt. Diese endliche Induktion dient in der Mathematik dem Finden von Hypothesen − hier kann sie sehr wertvoll sein −, aber ein Beweis von „für alle n gilt ℰ(n)“ ist auch dann nicht geführt, wenn die Eigenschaft ℰ für alle Zahlen 0, 1, 2, … 10¹⁰ nachgewiesen wurde. Um zu betonen, dass man nicht von Einzelfällen auf das Allgemeine schließt, ist im deutschsprachigen Raum die Sprechweise „vollständige Induktion“ populär. Oft spricht man aber auch nur von „Induktion“, da ohnehin klar ist, dass in der Mathematik keine unvollständigen Beweise akzeptiert werden. Im Englischen ist „(mathematical) induction“ üblich. Der Ausdruck „complete induction“ bedeutet im Englischen dagegen eine starke Form der Induktion, die wir in der nächsten Sektion besprechen.

Der Leser wird in seinen Vorlesungen oder in der Literatur die vollständige Induktion häufig als „Beweisprinzip“ bezeichnet sehen. Dagegen ist nichts einzuwenden, da der obige Satz tatsächlich eine Methode zur Verfügung stellt, die in Anwendungen so empfunden wird wie etwa das Prinzip des indirekten Beweisens. Dennoch gibt es Unterschiede: In der mengentheoretisch fundierten Mathematik ist die vollständige Induktion einfach ein beweisbarer Satz. Nur in der reinen Zahlentheorie betrachtet man die Induktion als Axiom.

Wir beschreiben nun, wie der Satz über die vollständige Induktion in der Praxis eingesetzt wird. Es liege also eine Behauptung

„Für alle n  ∈  ℕ gilt ℰ(n).“

vor, die wir beweisen möchten. Ein Induktionsbeweis zerfällt in zwei Teile:

Teil 1: Induktionsanfang

Wir beweisen, dass die Null die Eigenschaft ℰ besitzt.

Teil 2: Induktionsschritt von n nach n + 1

Der zweite und oft viel schwierigere Teil des Beweises ist der Induktionsschritt.

Dafür betrachten wir eine beliebige natürliche Zahl n, die für den Rest des Beweises nicht mehr verändert wird. Nun bekommen wir, ohne arbeiten zu müssen, ein Geschenk: Wir dürfen annehmen, dass n die Eigenschaft ℰ besitzt. Diese Gültigkeit von ℰ(n) heißt Induktionsvoraussetzung, abgekürzt I. V. − man sollte sie als „Induktionsgeschenk“ auffassen. Oft notiert man die Induktionsvoraussetzung suggestiv als: „Sei also ℰ(n) bereits bewiesen.“ Logisch korrekter ist eine schlichte Formulierung wie: „Es gelte also ℰ(n)“ oder „Wir nehmen ℰ(n) an.“ Nun müssen wir arbeiten und beweisen, dass n + 1 die Eigenschaft ℰ besitzt. Neben bereits bewiesenen einschlägigen Sätzen werden wir hierzu vor allem auch unser Geschenk einsetzen.

Nach Teil 1 und Teil 2 gelten die Voraussetzungen (a) und (b) des Satzes über die vollständige Induktion. Damit ist gezeigt, dass ℰ(n) für alle n gilt.

Beispiel

Sei x  ∈  ℝ mit x ≥ −1. Wir beweisen durch Induktion:

„Für alle n ≥ 0 gilt (1 + x)ⁿ ≥ 1 + n x.“

(Bernoulli-Ungleichung)

Die betrachtete Eigenschaft ℰ(n) lautet also

(1 + x)ⁿ ≥ 1 + n x.

Die reelle Zahl x ist hier ein sog.

Parameter der Eigenschaft ℰ.

Induktionsanfang n = 0:

Es gilt (1 + x)⁰ = 1 ≥ 1 + 0 x. Also gilt ℰ(0).

Induktionsschritt von n nach n + 1:

Sei n eine beliebige natürliche Zahl. Es gelte (1 + x)ⁿ ≥ 1 + n x (dies ist die Induktionsvoraussetzung ℰ(n)). Dann gilt ℰ(n + 1), denn

(1 + x)^n + 1 = (1 + x)ⁿ (1 + x) ≥ _{I. V. und x ≥ −1} (1 + n x) (1 + x) =

1 + n x + x + n x² ≥ _{n x² ≥ 0} 1 + n x + x = 1 + (n + 1) x.

Damit ist die Bernoulli-Ungleichung für x bewiesen.