1.4 Vollständige Induktion

Grundidee

Viele mathematische Behauptungen bestehen aus unendlich vielen Einzelaussagen:

\[a(n_0),\;a(n_0+1),\;a(n_0+2),\ldots\]

Die vollständige Induktion verbindet einen sicheren Start mit einem Schritt, der die Gültigkeit jeweils an die nächste natürliche Zahl weitergibt.

Abbildung 1.1: Domino-Modell der vollständigen Induktion: Der Induktionsanfang stößt den ersten Stein an, der Induktionsschritt überträgt die Aussage auf den nächsten Stein.

Das Induktionsprinzip

Das Induktionsprinzip formuliert nun präzise, welche beiden Schritte für einen Beweis über alle natürlichen Zahlen ausreichen.

Satz 1.6 (Prinzip der vollständigen Induktion). Für jedes \(n\in\mathbb N\) mit \(n\ge n_0\) sei \(a(n)\) eine Aussage. Gelten

  1. Induktionsanfang: \(a(n_0)\) ist wahr, und
  2. Induktionsschritt: Für jedes feste \(n\ge n_0\) gilt \(a(n)\Rightarrow a(n+1)\),

dann ist \(a(n)\) für alle \(n\ge n_0\) wahr.

Abbildung 1.1 veranschaulicht beide Voraussetzungen: Ohne den ersten fallenden Stein beginnt nichts; sobald ein Stein fällt, fällt auch der darauf folgende.

Beweisaufbau

Ein Induktionsbeweis wird immer sichtbar in drei Schritte (Induktionsanfang IA, Induktionsvoraussetzung IV, Induktionsschritt IS) gegliedert:

  1. IA: Zeige \(a(n_0)\).
  2. IV: Nimm \(a(n)\) für ein festes, aber beliebiges \(n\ge n_0\) an.
  3. IS: Zeige unter Verwendung der IV die Aussage \(a(n+1)\).

Die Induktionsvoraussetzung wird nicht für alle Zahlen gleichzeitig angenommen. \(n\) ist fest, aber beliebig. Im Induktionsschritt darf ausschließlich die Aussage für dieses \(n\) benutzt werden, um die Aussage für \(n+1\) herzuleiten.

Weitere Beispiele

Das erste ausführliche Beispiel zeigt das vollständige Beweisschema an einer Summenformel.

Beispiel: Summe der Quadrate

Aufgabenstellung. Beweisen Sie durch vollständige Induktion für jedes \(n\in\mathbb N\):

\[\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}6.\]

IA: Für \(n=1\) gilt

\[1^2=1=\frac{1\cdot2\cdot3}{6}.\]

IV: Für ein festes \(n\in\mathbb N\) gelte \(\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}\).

IS: Dann gilt

\[ \begin{aligned} \sum_{k=1}^{n+1}k^2 &=\sum_{k=1}^{n}k^2+(n+1)^2\\ &=\frac{n(n+1)(2n+1)}6+(n+1)^2\\ &=\frac{n+1}{6}\bigl(n(2n+1)+6(n+1)\bigr)\\ &=\frac{n+1}{6}\bigl(2n^2+7n+6\bigr)\\ &=\frac{n+1}{6}(n+2)(2n+3)\\ &=\frac{(n+1)\bigl((n+1)+1\bigr)\bigl(2(n+1)+1\bigr)}6. \end{aligned} \]

Damit ist die Behauptung für alle \(n\in\mathbb N\) bewiesen.

Im nächsten Beispiel wird mit der Induktionsvoraussetzung nicht eine Formel ausgerechnet, sondern eine Teilbarkeit übertragen.

Beispiel zur Teilbarkeit

Aufgabenstellung. Zeigen Sie durch vollständige Induktion, dass für jedes \(n\in\mathbb N\)

\[ 3\mid n^3+2n \]

gilt. Das Symbol \(3\mid n^3+2n\) bedeutet, dass \(n^3+2n\) durch \(3\) teilbar ist.

IA: Für \(n=1\) gilt \(1^3+2\cdot1=3\), die Behauptung ist also erfüllt.

IV: Für ein festes \(n\in\mathbb N\) sei \(n^3+2n\) durch \(3\) teilbar. Dann existiert ein \(k\in\mathbb Z\) mit \(n^3+2n=3k\).

IS: Für \(n+1\) erhalten wir

\[ \begin{aligned} (n+1)^3+2(n+1) &=n^3+3n^2+3n+1+2n+2\\ &=(n^3+2n)+3(n^2+n+1)\\ &=3\bigl(k+n^2+n+1\bigr). \end{aligned} \]

Da \(k+n^2+n+1\) eine ganze Zahl ist, ist auch der Ausdruck für \(n+1\) durch \(3\) teilbar. Damit gilt die Behauptung für alle \(n\in\mathbb N\).

Zum Abschluss zeigt eine Ungleichung, dass im Induktionsschritt häufig noch eine zusätzliche Abschätzung benötigt wird.

Beispiel zu einer Ungleichung

Aufgabenstellung. Beweisen Sie durch vollständige Induktion für alle \(n\geq5\):

\[ 2^n>n^2. \]

IA: Für \(n=5\) gilt \(2^5=32>25=5^2\).

IV: Für ein festes \(n\geq5\) gelte \(2^n>n^2\).

IS: Aus der Induktionsvoraussetzung folgt zunächst

\[ 2^{n+1}=2\cdot2^n>2n^2. \]

Nun müssen wir \(2n^2\) mit dem gewünschten rechten Term \((n+1)^2\) vergleichen. Für \(n\geq5\) gilt

\[ 2n^2-(n+1)^2=n^2-2n-1=(n-1)^2-2>0. \]

Somit ist \(2n^2>(n+1)^2\) und insgesamt \(2^{n+1}>(n+1)^2\). Die Behauptung gilt daher für alle \(n\geq5\).

Zusammenfassung

  • Die vollständige Induktion beweist eine Folge von Aussagen \(a(n)\) durch die Bestätigung der ersten Aussage und dem Nachweis, dass falls eine Aussage \(a(n)\) gilt, dann auch die Aussage \(a(n+1)\) wahr sein muss.
  • Ein Induktionsbeweis gliedert sich klar in Induktionsanfang, Induktionsvoraussetzung und Induktionsschritt.
  • In der Induktionsvoraussetzung ist \(n\) fest, aber beliebig; sie darf im Induktionsschritt verwendet werden, um genau die Aussage für \(n+1\) zu zeigen.
  • Das Verfahren eignet sich unter anderem für Summenformeln, Teilbarkeitsaussagen und Ungleichungen über natürlichen Zahlen.