Induktionsprinzip

Wir setzen weiterhin die natürlichen Zahlen als bekannt voraus, wollen aber ihre Eigenschafter etwas formaler beschreiben. Das kann auf verschieden Weisen geschehen.

Üblich ist das folgende Axiomensystem (Peano Axiome), das wir hier nur umgangssprachlich formulieren.

Die Axiome präzisieren den Vorgang des Zählens:

• Es gibt eine natürliche Zahl 1.
• Auf jede natürliche Zahl $n$ folgt eine nächste, die man mit $n+1$ bezeichnet.
• Man kann beim Zählen nicht mehrmals auf dieselbe Zahl stoßen. D.h. wenn zwei natürliche Zahlen $m,n$ denselben Nachfolger haben, sind sie gleich:
  $$m+1 = n+1 \quad\Rightarrow\quad m=n.$$

• Man kommt beim Zählen nicht zurück zur 1. D.h. für alle natürlichen Zahlen $n$ gil:
  $$n+1 \not= 1$$

• Man erreicht durch Zählen, ausgehend von der 1, alle natürlichen Zahlen.

Die zuletzt genannte Eigenschaft heißt das Induktionsprinzip. Wir formulieren es in der Sprache der Mengenlehre.

Feststellung 1.2.6 (Induktionsprinzip)   Es sei $M\subseteq \mathbb{N}$ ein Teilmenge der natürlichen Zahlen mit den Eigenschaften

a)

$1\in M$

b)

$n\in M \quad \Rightarrow \quad n+1 \in M$

Dann folgt schon $M=\mathbb{N}$

In den Anwendungen hat man eine Aussage $A(n)$ über eine natürliche Zahlen $n$. Die Aussage sei für alle natürlichen Zahlen formulierbar. Man möchte die Aussage $A(n)$ für jedes $n\in \mathbb{N}$ beweisen.

Dazu bilde man die Menge

$$M := \{n \mid n\in\mathbb{N},~ A(n)$$    ist richtig für $$n\}$$

und zeige mit Hilfe des Induktionsprinzips, daß $M=\mathbb{N}$ ist.

Dazu muß man für $M$ die Eigenschaften a) und b) nachweisen. Man kommt so zu dem folgendem Beweisprinzip:

Feststellung 1.2.7 (Vollständige Induktion)  

Für alle $n\in \mathbb{N}$ sei eine Aussage $A(n)$ gegeben. Es gelte:

Induktionsanfang:

$A(1)$ ist richtig .

Induktionsschritt:

Für alle $n\in \mathbb{N}$ gilt der Schluß:

$$A(n) \quad\Rightarrow\quad A(n+1).$$

Dann ist $A(n)$ für alle $n\in \mathbb{N}$ richtig.

Zum Beweis siehe Vorlesung oder [KABALLO, S. 13].

Beispiele 1.2.8 (Induktionsbeweise)   .

1. Dreiecksungleichung für endliche Reihen:
   $$\vert\sum_{k=1}^n a_k\vert \leq \sum_{k=1}^n \vert a_k\vert$$.$$$$

2. Summenformel der geometrischen Reihe:
   $$\sum_{k=0}^n x^k = \left\{\begin{array}{cl} \displaystyle \frac{1... ...\uml {u}r } x \not= 1\\ [2ex] n+1 &\mbox{f\uml {u}r } x=1. \end{array}\right.$$

3. Zweite binomische Formel:
   $$(x-y)\sum_{k=0}^n x^{n-k} y^k= x^{n+1}-y^{n+1}$$.$$$$

Zum Beweis siehe Vorlesung oder [KABALLO, S. 14].