Beweisverfahren der vollständigen Induktion

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)\text{Für alle}n\in \mathbb{N}\text{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

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:

1. Induktionsanfang
   Man zeigt, dass $H\left(1\right)$ wahr ist.
    
2. 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)\text{für alle}n\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[\text{Für alle}n\in \mathbb{N}:H\left(n\right)\Rightarrow H\left(n+1\right)\right]\Rightarrow \left[\text{Für alle}n\in \mathbb{N}:H\left(n\right)\right]\\ oder\\ H\left(n_0\right)\wedge \left[\text{Für alle}k\in \mathbb{N}:H\left(k\right)\Rightarrow H\left(k+1\right)\right]\Rightarrow \left[\text{Für alle}n\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$

1. 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}$
2. 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)$.

1. Induktionsanfang
   $n=0\text{:}{11}^2+12=133\Rightarrow 133|133$
2. Induktionsschritt
   Induktionsvoraussetzung (n = k):
   Es gelte $133|\left({11}^{k+1}+{12}^{2k-1}\right)$.
   Induktionsbehauptung (n = k + 1):
   Es 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)$.