# Dedekind-Peano-Axiome/Zählen/Induktionsprinzip/Minimum/Textabschnitt

Die folgende Aussage und ihr Beweis begründen das Beweisprinzip der vollständigen Induktion. Wir schreiben $n+1$ für den Nachfolger.

## Satz

Für jede natürliche Zahl $n$ sei eine Aussage $A(n)$ gegeben. Es gelte
* $A(0)$ ist wahr.
* Für alle $n$ gilt: wenn $A(n)$ gilt, so ist auch $A(n+1)$ wahr.
Dann gilt $A(n)$ für alle $n$.

### Beweis

Es sei
    $M={\left\{n\in \mathbb {N} \mid A(n){\text{ ist wahr}}\right\}}\,.$
Wir wollen zeigen, dass $M=\mathbb {N}$ ist, denn genau dies bedeutet, dass die Aussage für alle $n$ gilt. Nach der ersten Bedingung ist
    $0\in M\,.$
Nach der zweiten Voraussetzung gilt für $M$, dass aus $n\in M$ stets $n+1\in M$ folgt. Damit erfüllt $M$ beide Voraussetzungen im Induktionsprinzip für Mengen, sodass $M=\mathbb {N}$ gilt.
$\Box$
Der Nachweis von (der Gültigkeit von) $A(0)$ heißt dabei der Induktionsanfang und der Schluss von $A(n)$ auf $A(n+1)$ heißt der Induktionsschluss oder Induktionsschritt. Innerhalb des Induktionsschlusses nennt man die Gültigkeit von $A(n)$ auch die Induktionsvoraussetzung. In manchen Situationen ist die Aussage $A(n)$ erst für $n\geq n_{0}$ für ein gewisses $n_{0}$ (definiert oder) wahr. Dann beweist man im Induktionsanfang die Aussage $A(n_{0})$ und den Induktionsschritt führt man für alle $n\geq n_{0}$ durch.
Um dieses Beweisprinzip anhand von substantiellem Material demonstrieren zu können, greifen wir etwas vor und setzen die Addition, die Multiplikation und die Größergleichrelation von natürlichen Zahlen voraus. Das folgende Standardbeispiel für einen Induktionsbeweis verwendet das Summenzeichen. Für gegebene (natürliche, reelle) Zahlen $a_{1},\ldots ,a_{n}$ bedeutet
    $\sum _{k=1}^{n}a_{k}:=a_{1}+a_{2}+\cdots +a_{n-1}+a_{n}\,.$
Dabei hängen typischerweise die $a_{k}$ in einer formelhaften Weise von $k$ ab. Entsprechend ist das Produktzeichen definiert, nämlich durch
    $\prod _{k=1}^{n}a_{k}:=a_{1}\cdot a_{2}{\cdots }a_{n-1}\cdot a_{n}\,.$

## Aufgabe

Beweise durch Induktion die folgende Formel für $n\geq 1$.
    $\sum _{k=1}^{n}k={\frac {n(n+1)}{2}}\,.$
Lösung
Beim Induktionsanfang ist $n=1$, daher besteht die Summe links nur aus einem Summanden, nämlich der $1$, und daher ist die Summe $1$. Die rechte Seite ist ${\frac {1\cdot 2}{2}}=1$, sodass die Formel für $n=1$ stimmt.
Für den Induktionsschritt setzen wir voraus, dass die Formel für ein $n\geq 1$ gilt, und müssen zeigen, dass sie auch für $n+1$ gilt. Dabei ist $n$ beliebig. Es ist
    ${\begin{aligned}\sum _{k=1}^{n+1}k&=\left(\sum _{k=1}^{n}k\right)+n+1\\&={\frac {n(n+1)}{2}}+n+1\\&={\frac {n(n+1)+2(n+1)}{2}}\\&={\frac {(n+2)(n+1)}{2}}.\end{aligned}}$
Dabei haben wir für die zweite Gleichheit die Induktionsvoraussetzung verwendet. Der zuletzt erhaltene Term ist die rechte Seite der Formel für $n+1$, also ist die Formel bewiesen.
Aussagen, die durch Induktion bewiesen werden können, können manchmal auch auf andere Art bewiesen werden. Im vorstehenden Beispiel gibt es die elegantere und einsichtigere Lösung, die Zahlen einmal aufsteigend und einmal absteigend untereinander hinzuschreiben, also
    $1\,\,\,\,\,\,\,\,\,\,\,\,2\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,3\,\,\,\,\ldots \,\,\,\,n-2\,\,\,\,n-1\,\,\,\,n$
    $n\,\,\,\,\,n-1\,\,\,\,\,\,n-2\,\,\,\,\ldots \,\,\,\,3\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,2\,\,\,\,\,\,\,\,\,\,\,\,1$
Spaltenweise ergibt sich $n+1$, und diese Summe kommt $n$-mal vor. Also ist
    $2{\left(\sum _{i=1}^{n}i\right)}=n{\left(n+1\right)}\,.$

## Aufgabe

Zeige durch vollständige Induktion, dass für jedes $n\in \mathbb {N}$ die Zahl
    $6^{n+2}+7^{2n+1}$
ein Vielfaches von $43$ ist.
Lösung
Induktionsanfang. Für $n=0$ ist
    $6^{2}+7=43\,$
ein Vielfaches von $43$. Induktionsschritt. Es sei nun die Aussage für $n$ bewiesen und betrachten wir den Ausdruck für $n+1$. Dieser ist
    ${\begin{aligned}6^{n+1+2}+7^{2(n+1)+1}&=6\cdot 6^{n+2}+7^{2}\cdot 7^{2n+1}\\&=6\cdot 6^{n+2}+(6+43)7^{2n+1}\\&=6{\left(6^{n+2}+7^{2n+1}\right)}+43\cdot 7^{2n+1}\\&=6\cdot 43\cdot s+43\cdot 7^{2n+1}\\&=43\cdot {\left(6\cdot s+7^{2n+1}\right)},\end{aligned}}$
wobei im vorletzten Schritt die Induktionsvoraussetzung verwendet wurde (nämlich die Eigenschaft, dass $6^{n+2}+7^{2n+1}$ ein Vielfaches von $43$ ist). Daher ist diese Zahl ein Vielfaches von $43$.
Aus dem Induktionsprinzip folgt die nächste wichtige Eigenschaft. Vom intuitiven Standpunkt her ist sie selbstverständlich, wir führen sie aber trotzdem auf das Induktionsprinzip zurück. Es geht in diesem Beweis weniger dadrum, sich über die Satzaussage zu vergewissern, sondern vielmehr Einblicke in mathematisches Argumentieren zu gewinnen. Es ist auch ein Beispiel dafür, wie man eine Aussage über Teilmengen zu einer Aussage über natürliche Zahlen macht, um das Induktionsprinzip anwenden zu können.

## Lemma

Jede nichtleere Teilmenge $M\subseteq \mathbb {N}$
besitzt ein Minimum.

### Beweis

Wir betrachten die Aussage
    $A(n)$ = Alle Teilmengen von $\mathbb {N}$, die $n$ enthalten, besitzen ein Minimum.
Da jede nichtleere Teilmenge mindestens ein $n\in \mathbb {N}$ besitzt, ist die Aussage des Satzes äquivalent zur Gültigkeit von $A(n)$ für alle $n$. Diese Aussage können wir durch Induktion beweisen. Die Aussage $A(0)$ besagt, dass jede Teilmenge $M\subseteq \mathbb {N}$, die die $0$ enthält, auch ein Minimum enthält. Dies ist aber klar, da dann eben $0$ das Minimum ist. Es sei die Aussage $A(k)$ nun für alle $k\leq n$ schon bewiesen. Wir müssen $A(n+1)$ beweisen. Es sei also $M\subseteq \mathbb {N}$ eine Teilmenge, die $n+1$ enthält. Wenn $M$ auch eine Zahl $k<n+1$ besitzt, so besitzt $M$ nach der Induktionsvoraussetzung ein Minimum. Andernfalls besitzt $M$ keine Zahl, die kleiner als $n+1$ ist. Dann ist aber $n+1$ das Minimum von $M$.
$\Box$