Beweise, vollständige Induktion

Das Verfahren der vollständigen Induktion hängt eng zusammen mit der Menge der natürlichen Zahlen bzw. mit Teilmengen natürlicher Zahlen. Es ist immer dann anwendbar, wenn man auf Aussagen trifft, die für alle natürlichen Zahlen gelten, also die die folgende Struktur aufweisen:

Für alle natürlichen Zahlen $n(mitn\ge n_0)$ gilt $H\left(n\right)$.

Das Verfahren beruht auf der sogenannten Induktionseigenschaft der natürlichen Zahlen. Diese ist Bestandteil des peanoschen Axiomensystems und lautet:

Ist T eine Teilmenge von $\mathbb{N}$ und gilt
$\begin{array}{l}(I)1\in T\\ (II)Fürallen\in \mathbb{N}gilt:n\in T\iff n+1\in T,\end{array}$
dann ist $T=\mathbb{N}$.

Es sei $T=\left\{n:H\left(n\right)\right\}$ die Menge aller natürlichen Zahlen, für die eine Aussage $H\left(n\right)$ wahr ist.
Anwenden der Induktionseigenschaft besagt dann das Folgende.
Wenn man zeigen kann
$\begin{array}{l}a)H\left(1\right)istwahr,d.h.1\in T.\\ b)Fürallengilt:WennH\left(n\right)wahrist,soistH\left(n+1\right)wahr.\\ n\in T\Rightarrow n+1\in Tfürallen\in \mathbb{N}\end{array}$
dann gilt (aufgrund der als Axiom angenommenen Induktionseigenschaft) $T=\mathbb{N}$, was wiederum bedeutet $H\left(n\right)$ ist für alle $n\in \mathbb{N}$ gültig.

Um die Allgemeingültigkeit einer Aussage $H\left(n\right)$ über $\mathbb{N}$nachzuweisen, hat man also beim Beweis durch vollständige Induktion zwei Schritte zu vollziehen:

• Induktionsanfang
  Man zeigt, dass $H\left(1\right)$ wahr ist.
• Induktionsschritt
  Man zeigt, dass für alle $n\in \mathbb{N}$ gilt: Aus der Annahme, $H\left(n\right)$ sei richtig, kann auf die Gültigkeit von $H\left(n+1\right)$ geschlossen werden, d. h.:
  $H\left(n\right)\Rightarrow H\left(n+1\right)fürallen\in \mathbb{N}$
  (Inhalt des Induktionsschrittes ist also eine Implikation $A\Rightarrow B$. Das Vorderglied heißt Induktionsvoraussetzung und das Hinterglied dieser Implikation ist die Induktionsbehauptung.)

Wichtig ist, dass beide Schritte verifiziert werden müssen, d. h. als wahr nachzuweisen sind: sowohl der Induktionsanfang (es muss erst einmal eine natürliche Zahl geben, für die $H\left(n\right)$ gilt) als auch der Induktionsschritt oder Induktionsschluss (Nachweis der obigen Implikation). Erst dann gilt, dass $H\left(n\right)$ für alle wahr $n\in \mathbb{N}$ ist.

Die Struktur des Beweises durch vollständige Induktion sieht formal also folgendermaßen aus:
$\begin{array}{l}H\left(1\right)\wedge \left[Fürallen\in \mathbb{N}:H\left(n\right)\Rightarrow H\left(n+1\right)\right]\Rightarrow \left[Fürallen\in \mathbb{N}:H\left(n\right)\right]\\ oder\\ H\left(n_0\right)\wedge \left[Fürallek\in \mathbb{N}:H\left(k\right)\Rightarrow H\left(k+1\right)\right]\Rightarrow \left[Fürallen\ge n_0:H\left(n\right)\right]\end{array}$

Beispiel 1:

Man beweise durch vollständige Induktion:
${\displaystyle \sum _{i=1}^n{i}^3=1^3+2^3}+3^3+\mathrm{...}+n^3={\left[\frac{n\left(n+1\right)}{2}\right]}^2$

• Induktionsanfang
  $\begin{array}{c}n=1\text{:}{\displaystyle \sum _{i=1}^1{i}^3}=1^3={\left(\frac{1\left(1+1\right)}{2}\right)}^2\\ 1=1\end{array}$
• Induktionsschritt
  Induktionsvoraussetzung (n = k):
  Es gelte ${\displaystyle \sum _{i=1}^k{i}^3=1^3+2^3}+3^3+\mathrm{...}+k^3={\left[\frac{k\left(k+1\right)}{2}\right]}^2$.
  Induktionsbehauptung (n = k + 1):
  Es sei ${\displaystyle \sum _{i=1}^{k+1}{i}^{\text{‌}3}=1^3+2^3}+3^3+\mathrm{...}+k^3+{\left(k+1\right)}^3={\left[\frac{\left(k+1\right)\left(k+2\right)}{2}\right]}^2$.
  Induktionsbeweis:
  $\begin{array}{l}{\displaystyle \sum _{i=1}^{k+1}{i}^3={\displaystyle \sum _{i=1}^{k}i{}^3}}+{\left(k+1\right)}^3\\ ={\left[\frac{k(k+1)}{2}\right]}^2+{\left(k+1\right)}^3\\ =\frac{k^2{(k+1)}^2+4{(k+1)}^3}{4}=\frac{k^2{(k+1)}^2+4{(k+1)}^2\cdot (k+1)}{4}\\ =\frac{{(k+1)}^2\cdot (k^2+4k+4)}{4}=\frac{{(k+1)}^2\cdot {(k+2)}^2}{4}\\ ={\left[\frac{(k+1)\cdot (k+2)}{2}\right]}^2\end{array}$

Beispiel 2:

Man beweise: Für alle $n\in \mathbb{N}$ gilt $133|\left({11}^{n+2}+{12}^{2n+1}\right)$.

• Induktionsanfang
  $n=0\text{:}{11}^2+12=133\Rightarrow 133|133$
• Induktionsschritt
  Induktionsvoraussetzung (n = k − 1):
  Es gelte $133|\left({11}^{k+1}+{12}^{2k-1}\right)$.
  Induktionsbehauptung (n + 1 = k):
  Dann sei auch $133|\left({11}^{k+2}+{12}^{2k+1}\right)$.
  Induktionsbeweis:
  $\begin{array}{c}{11}^{k+2}+{12}^{2k+1}={11}^{k+1}\cdot 11+{12}^{2k-1}\cdot {12}^2\\ ={11}^{k+1}+10\cdot {11}^{k+1}+{12}^{2k-1}+143\cdot {12}^{2k-1}\\ ={11}^{k+1}+{12}^{2k-1}+10\cdot {11}^{k+1}+143\cdot {12}^{2k-1}\\ =\underset{nachVoraussetzung\text{‌}\text{‌}\text{‌}durch133teilbar}{\underbrace{{11}^{k+1}+{12}^{2k-1}+10\left({11}^{k+1}+{12}^{2k-1}\right)}}+133\cdot {12}^{2k-1}\\ \end{array}$
  Folglich gilt $133|\left({11}^{n+2}+{12}^{2n+1}\right)$.