(6) Einschub: Vollständige Induktion und Rekursion

\underline{(10.18) BEISPIEL:} Nachweis der Formel ∀ n ∈ IN : ∑_{k=1}^{n} k = \frac{1}{2}n(n + 1) mit Hilfe

vollständiger Induktion.

\underline{(10.19) SATZ:} Beweis durch vollständige Induktion

n_{0} ∈ IN sei eine feste Zahl, und es sei A(n) eine Aussage in Abhängigkeit von n ∈ IN. Kann man dann beweisen:

i) A(n_{0}) ist richtig,

ii) Aus der Richtigkeit von A(n) für eine beliebige, aber feste natürliche Zahl n ≥ n_{0} folgt die Richtigkeit von A(n + 1),

so ist A(n) für alle natürlichen Zahlen n ≥ n_{0} richtig.

Formal läßt sich ii) schreiben als ∀ n ∈ IN , n ≥ n_{0} : A(n) ⟹ A(n + 1)

Bezeichnungen: Ein Induktionsbeweis besteht immer aus 2 Beweis–Teilen:

1) dem Induktionsanfang (IA)

hier wird bewiesen, daß die Behauptung für n = n_{0} richtig ist

2) dem Induktionsschluß (IS) oder dem “Schluß von n auf n + 1“:

hier wird unter der Induktionsvoraussetzung (IV), daß die Behauptung für eine beliebige (aber feste) natürliche Zahl n ≥ n_{0} richtig ist, die Induktionsbehauptung (IB) bewiesen, daß dann die Behauptung auch für n + 1 richtig ist.

Grundlage für diese Beweismethode ist das sog. Induktionsprinzip aus den Peano–Axiomen für die natürlichen Zahlen:

(10.20) Die PEANO–Axiome für die natürlichen Zahlen:

P_{1}) 0 ist eine natürliche Zahl

P_{2}) Jede natürliche Zahl n besitzt eine natürliche Zahl n′ als Nachfolger

P_{3}) 0 ist nicht Nachfolger einer natürlichen Zahl

P_{4}) Haben zwei natürliche Zahlen denselben Nachfolger, so sind sie gleich

P_{5}) Induktionsprinzip

Eine Menge T natürlicher Zahlen, die 0 enthält und mit jeder Zahl auch deren Nachfolger, enthält alle natürlichen Zahlen.

Chr.Nelius: Lineare Algebra I (WS 2004/05) 2 Unter den Voraussetzungen i) und ii) aus (10.19) läßt sich zeigen, daß die Menge

T := { n | n ∈ IN, n ≥ n_{0}, A(n) ist richtig } ⊆ IN

auf Grund von P_{5}) gleich der Menge aller natürlichen Zahlen ≥ n_{0} ist, d.h. A(n) ist dann für alle n ∈ IN, n ≥ n_{0} richtig. Das Induktionsprinzip steht in engem Zusammenhang mit der sog. Wohlordung der natürlichen Zahlen: \underline{(10.21) SATZ:} Die geordnete Menge (IN, ≤) ist wohlgeordnet, d.h. jede nichtleere Teilmenge von IN besitzt ein kleinstes Element. Man kann die Wohlordnung von (IN, ≤) mit Hilfe des Induktionsprinzips P_{5}) beweisen und umgekehrt aus der Wohlordnung von (IN, ≤) das Induktionsprinzip folgern.