Inhalt
» Was ist vollständige Induktion
» Ein Beispiel
» Tipps zum Führen von Induktionsbeweisen

Was ist vollständige Induktion?

Das Verfahren der vollständigen Induktion wird meistens dann verwendet, wenn eine Behauptung für alle natürlichen Zahlen gezeigt werden soll. Es funktioniert mit einer Art Dominoeffekt: Wir müssen es am Anfang einmal anstoßen (Induktionsanfang) und wir müssen dafür sorgen, dass jeder Dominostein seinen Nachfolger umstößt (Induktionsschritt).

Etwas mathematischer formuliert: Für jedes \(n\in \mathbb{N}\) sei \(A(n)\) eine Aussage (in Abhängigkeit von \(n\), sonst funktioniert die Induktion nicht). Der Induktionsbeweis besteht aus

  • Induktionsanfang: Zeige, dass \(A(1)\) wahr ist.
  • Induktionsvoraussetzung (oder Induktionsannahme): \(A(m)\) gilt.
  • Induktionsbehauptung: \(A(m+1)\) gilt.
  • Induktionsschluss (oder -beweis oder -schritt): Zeige die Induktionsbehauptung mit Hilfe der Induktionsvoraussetzung.

Dann ist \(A(n)\) für jedes \(n\in\mathbb{N}\) wahr. Induktionsvoraussetzung, -behauptung und -schluss werden oft unter dem Begriff Induktionsschritt zusammengefasst.

Ein Beispiel

Ein schönes Beispiel, bei dem man vollständige Induktion verwenden kann, ist die Gaußsche Summenformel: Für alle \(n\geq 1\) gilt \(\sum_{k=1} ^n k = \frac{n(n+1)}{2}\).

Induktionsanfang: Wir zeigen, dass die Formel für \(n=1\) richtig ist: \begin{align*} \sum_{k=1}^1 k = 1 = \frac{2}{2} = \frac{1(1+1)}{2} \end{align*}

Induktionsschritt: Sei \(m\in\mathbb{N}\) und die Summenformel sei für \(n=m\) bereits bewiesen. Wir zeigen, dass die Formel auch für \(n=m+1\) gilt: \begin{align*} \sum_{k=1}^{m+1} k &= (\sum_{k=1}^m k) + (m+1) \\&= \frac{m(m+1)}{2} + \frac{2(m+1)}{2} \\&= \frac{(m+2)(m+1)}{2} \\&= \frac{(m+1)((m+1)+1)}{2} \end{align*}

 

 

Tipps zum Führen von Induktionsbeweisen

Oft ist es relativ einfach, den Induktionsanfang zu zeigen, und etwas schwerer, den Induktionsschritt zu zeigen. Wie kommt man also auf den Beweis des Induktionsschritts?

Zuerst hilft es, einen Weg zu suchen, um die Induktionsannahme zu benutzen. In unserem Beispiel haben wir dazu den letzten Summanden aus dem Summenzeichen herausgezogen, und konnten sofort die Annahme, dass die Formel für \(n=m\) gilt, verwenden.

Danach darf man das Ziel nicht aus den Augen verlieren. Auf einem Schmierzettel kann man den Beweis von beiden Seiten anfangen und hoffen, dass sich die Anfänge irgendwann treffen. Erst dann schreibt man die Rechnung ordentlich von links nach rechts auf.