# Vollständige Induktion/Einführung/Textabschnitt

Die natürlichen Zahlen sind dadurch ausgezeichnet, dass man mit ihnen zählen kann, d.h. dass man in ihnen ausgehend von $0$ durch den Übergang von $n$ zum Nachfolger $n'=n+1$ jede natürliche Zahl erreicht. Dies begründet die folgende Eigenschaft: Wenn $T\subseteq \mathbb {N}$ eine Teilmenge ist, die einerseits die $0$ enthält und die andererseits mit jedem $n\in T$ auch den Nachfolger enthält (also $n+1\in T$), so ist bereits $T=\mathbb {N}$. Mit dem Startglied $0$ folgt ja dann zunächst $1\in T$, sodann $2\in T$, sodann $3\in T$ u.s.w, und da dieser Zählprozess jede natürliche Zahl erreicht, gehört jede natürliche Zahl zu $T$. Diese Beobachtung ist die Grundlage der vollständigen Induktion.
Mathematische Aussagen, die von natürlichen Zahlen abhängen, können mit dem Beweisprinzip der vollständigen Induktion bewiesen werden. Die folgende Aussage begründet dieses Prinzip.

## 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. 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 Induktionsschluss führt man für $n\geq n_{0}$ durch.
Das folgende Standardbeispiel für einen Induktionsbeweis verwendet das Summenzeichen. Für gegebene (natürliche, reelle, komplexe) 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 im Allgemeinen 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}\,.$
Insbesondere sind für $n\in \mathbb {N}$ die Potenzen durch
    $a^{n}=\prod _{i=1}^{n}a=a^{n-1}\cdot a=\underbrace {a\cdot a{\cdots }a} _{n{\text{-mal}}}\,$
definiert. Dabei gelten die Konventionen $0a=0$ und $a^{0}=1$ (die erste lässt sich auch über die Multiplikation begründen, die zweite ist aber auch sinnvoll). Als Rechenregeln für das Potenzieren gelten
    $(a\cdot b)^{n}=a^{n}\cdot b^{n}\,$
    $a^{n+m}=a^{n}\cdot a^{m}\,$
    $(a^{n})^{m}=a^{nm}\,.$

## 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.

## 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$.