Vollständige Induktion

In diesem Artikel beschäftigen wir uns mit einer eigenen Beweisstrategie, der sogenannten vollständigen Induktion. Diese Art des Beweisens ist immer dann hilfreich, wenn eine Aussage $A(n)$ für alle natürlichen Zahlen oder alle natürlichen Zahlen ab einer bestimmen Zahl bewiesen werden soll. Die Beweistechnik beruht auf der namensgebenden Induktivität der natürlichen Zahlen und orientiert sich an den folgenden drei Schritten:

Vorgehen der vollständigen Induktion:

Induktionsanfang
Hier wird die Gültigkeit der zu beweisenden Aussage für einen Startwert nachgerechnet. Oft wird hier beispielsweise die Gültigkeit $A(1)$ gezeigt.
Induktionsvoraussetzung
Diese wird hin und wieder weggelassen, sollte der Vollständigkeit halber allerdings stets aufgeführt werden. Die Induktionsvoraussetzung ist dabei reine Schreibarbeit und bedarf keiner Rechnung. Hier empfiehlt es sich einen Satz auswendig zu lernen und diesen an diese Stelle zu schreiben. Ein Beispiel wäre Die zu beweisende Aussage $A(n)$ gelte für ein $n\in\mathbb{N}$ beliebig.
Induktionsschritt
Der letzte Schritt der Induktion beweist die Gültigkeit für $A(n+1)$ indem bereits angenommen wird, dass $A(n)$ gültig ist. Es sollte beim Induktionsschritt also stets versucht werden, die eigentliche Aussage, also die Induktionsvoraussetzung, zu verwenden.

Anschaulich lässt sich die Induktion wie eine Dominoreihe erklären. Der Induktionsanfang sagt uns, dass beispielsweise der erste Dominostein umfällt. Die Induktionsvoraussetzung in Verbindung mit dem Induktionsschritt stellt nun sicher, dass jeder Dominostein, der umfällt, auch seinen Nachfolger zum Umfallen bringt. Dies resultiert nun darin, dass alle Dominosteine umfallen. Als Nächstes betrachten wir verschiedene Beispiele zu diesem Thema.

Beispiel
Wir möchten den kleinen Gauß mit Hilfe der Induktion beweisen. Unsere Aussage $A(n)$ lautet:

\begin{align*}
\text{Für alle }n\in\mathbb{N} \text{ gilt: }\sum_{k=0}^n k =\frac{n\cdot(n+1)}{2}
\end{align*}

Wir starten zunächst mit dem Induktionsanfang, hier $n = 1$. Merke: Da die Aussage für wirklich alle natürlichen Zahlen gelten soll, muss als Induktionsanfang hier $n=1$ gewählt werden! Es gilt:

1. Induktionsanfang: $n=1$: $\sum_{k=0}^1 k = 0 + 1 = 1$ und $\frac{1\cdot(1+1)}{2} = \frac{2}{2} = 1$

2. Induktionsvoraussetzung: Die Aussage $A(n)$ gelte für ein $n\in\mathbb{N}$ beliebig.

3. Induktionsschritt $n \rightarrow n+1$:

\begin{align*}
\displaystyle\sum_{k=0}^{n+1} k &= (n+1)+\displaystyle\sum_{k=0}^n k = (n+1)+\frac{n\cdot(n+1)}{2} \quad \text{(I.V.)} \\
&=\frac{2\cdot(n+1)}{2}+\frac{n\cdot(n+1)}{2} =\frac{2\cdot(n+1)+n\cdot(n+1)}{2} =\frac{(n+1)\cdot(n+2)}{2}
\end{align*}

Dabei haben wir im ersten Schritt den letzten Summanden explizit außerhalb der Summe hingeschrieben, während wir die restlichen $n$ Summanden als Summe beschreiben. Dies ist bei solchen Aufgaben der vollständigen Induktion mit Summen ein probates Mittel, um die Induktionsvoraussetzung anzuwenden, welches wir im zweiten Schritt gemacht haben. Im letzten Schritt erhalten wir $\frac{(n+1)\cdot(n+2)}{2}$, also genau den Wert der rechten Seite der Aussage $A(n+1)$. Damit ist der Beweis erbracht.

Beispiel In diesem Fall lautet die Aussage $A(n)$: $\text{Für alle }n\in\mathbb{N}\text{ gilt: } n^3+2n \text{ ist durch }3\text{ teilbar.}$

Obwohl diese Aufgabe anders aussieht, gehen wir genau gleich vor:

1. Induktionsanfang $n=1$: $1^3+2\cdot 1 = 3$ und damit durch 3 teilbar

2. Induktionsvoraussetzung: Die Aussage $A(n)$ gelte für ein $n\in\mathbb{N}$ beliebig.

3. Induktionsschritt $n \rightarrow n+1$:

\begin{align*}
(n+1)^3+2\cdot(n+1)&=(n+1)\cdot((n+1)^2+2) =(n+1)\cdot(n^2+2n+1+2)\\
&=n^3+2n^2+3n+n^2+2n+3 =(n^3+2n)+(3n^2+3n+3)\\
&=n^3+2n+3\cdot(n^2+n+1)
\end{align*}

Nach der Induktionsvoraussetzung ist $n^3+2n$ durch 3 teilbar und da $3\cdot(n^2+n+1)$ ein Vielfaches von 3 ist, ist der Term ebenfalls durch 3 teilbar. Da beide Summanden durch $3$ teilbar sind, ist auch die Summe durch $3$ teilbar. Damit gilt der Induktionsschritt und wir haben die Aussage bewiesen.