Prinzip der vollständigen Induktion
formuliert in: Vollständige Induktion/ Das Prinzip der vollständigen Induktion
Sei mit „E(n)“ irgendeine Aussage bezeichnet, die in
Abhängigkeit von n ∈∈ ℕ
formuliert werden kann. Wenn „ℰ(n)“
die Abkürzung für „Die Aussage E(n) ist wahr“ bedeutet, dann lautet
das Prinzip der vollständigen Induktion wie folgt:
Gilt für m ∈∈ ℕ
(i) ℰ(0)
und
(ii) ℰ(m) ⇒ ℰ(succ(m)),
so folgt: ℰ(n) für alle n ∈∈ ℕ.
(i) heißt Induktionsanfang und (ii) heißt Induktionsschluss.
„ℰ(m)“
heißt
Induktionsvoraussetzung (oder Induktionsannahme).
Das Prinzip der vollständigen Induktion ergibt sich unmittelbar aus dem folgenden Peano’schen Axiom:
Sei M eine Teilmenge von ℕ mit den folgenden
zwei Eigenschaften:
(i) 0 ∈∈ M
(ii) m ∈∈ M ⇒ succ(m) ∈∈ M.
Dann folgt: M = ℕ.
Einige Beispiele für Induktionsbeweise findet man beispielweise im Abschnitt Spezielle Folgen und Reihen.
→ Index
