Inhalt

Das Wichtigste in Kürze

Die vollständige Induktion ist eine Beweismethode für diskrete Problemstellungen (natürlicher Zähler). Eine Behauptung (meistens eine Formel) wird in zwei Schritten bewiesen:

    • Nachweis des Induktionsanfangs: z.B. für \(n=1\)
    • Nachweis des Induktionsschritts, meist für \(k \rightarrow k+1\)

Der Induktionsanfang wird durch einfaches Einsetzen überprüft:

\[ a_1 \; \unicode{x2714} \]

Der Induktionsschritt ist meistens etwas anspruchsvoller. Hier wir die Annahme gemacht, dass die Behauptung für irgendein \(k\)-tes Glied erfüllt ist. Dann wird gezeigt, dass daraus folgt, dass das nächste Glied für \(k+1\) die Behauptung erfüllt:

\[ a_k \; (\unicode{x2714}) \quad \Rightarrow \quad a_{k+1} \; \unicode{x2714} \]

Aus der Kombination von Induktionsanfang und Induktionsschritt folgt, dass die gesamte Folge die Behauptung erfüllt.

Die vollständige Induktion ist eine Beweismethode für diskrete Problemstellungen, typischerweise im Zusammenhang mit Folgen und Reihen. Eigentlich ist sie nicht so schwer, aber der Teufel liegt bekanntlich im Detail. Vielleicht musst du das Folgende mehrfach lesen. Schau Dir unbedingt die Beispiele an…das wird helfen. Irgendwann macht es dann “Klick”! 👍

Wir können mit der Methode der vollständigen Induktion eine ganze Folge oder Reihe beweisen und brauchen dazu im wesentlichen zwei Rechnungen auszuführen:

  • Nachweis des Induktionsanfangs: z.B. für \(n=1\)
  • Nachweis des Induktionsschritts, meist für \(k \rightarrow k+1\)

Wir haben eine Behauptung, meistens eine Formel ist, die wir zu beweisen haben.

Mit dem Induktionsanfang zeigen wir, dass die Behauptung für das erste Glied \(a_1\) erfüllt ist. Wir setzen einfach ein, rechnen dieses erste Glied aus und schauen, ob die Behauptung erfüllt ist.

Das ist schnell gemacht, beweist aber nur gerade, dass die Behauptung für dieses erste Glied \(a_1\) gilt.

\[ a_1 \; \unicode{x2714} \]

Wir könnten die Sache wiederholen und das zweite Glied \(a_2\) berechnen. Das Problem: Wir hätten damit auch nur gerade gezeigt, dass die Behauptung für \(a_2\) gilt und nicht für alle nachfolgenden Glieder.

\[ a_1 \; \unicode{x2714}, \;\; a_2 \; \unicode{x2714}, \;\; a_3 \; ?, \;\; a_4 \; ?, \;\; … \;\; a_n \; ?\]

Deshalb machen wir das nicht, sondern machen jetzt den Induktionsschritt mit der Grundannahme, dass die Behauptung für irgendein \(k\)-tes Glied \(a_k\) gilt. Haben wir nicht bewiesen, wir sagen einfach…“Unter der Annahme, dass die Behauptung für \(a_k\) gilt…”

Das ist sehr wichtig und hat mich damals immer wieder verwirrt. Wir haben bis hierhin nämlich nur nachgewiesen, dass die Behauptung für \(a_1\) gilt. Jetzt nehmen wir an, dass sie für \(a_k\) gilt.

Basierend auf dieser Annahme \((\unicode{x2714})\), berechnen wir das Resultat für das nächste Glied \(a_{k+1}\) und weisen nach, dass die Behauptung gilt \(a_{k+1}\; \unicode{x2714}\)

\[ a_k \; (\unicode{x2714}) \quad \Rightarrow \quad a_{k+1} \; \unicode{x2714} \]

Wir haben ja schon nachgewiesen, dass die Behauptung für \(a_1\) gilt. Jetzt wissen wir, dass basierend auf \(a_1\) die Behauptung nun auch für \(a_2\) gelten muss. Jetzt, wo ich bewiesen habe, dass sie für \(a_2\) gilt, gilt sie für \(a_3\). Jetzt, wo ich weiss, dass sie für \(a_3\) gilt, gilt sie auch für \(a_4\) usw.

“Wenn wir zeigen, dass ein fallender Dominostein den nächsten zu Fall bringt und wir gezeigt haben, dass er erste Dominostein fällt, haben wir bewiesen, dass alles fallen wird.”

Vollständige Induktion: Wenn wir zeigen, dass ein fallender Dominostein den nächsten zu Fall bringt und wir gezeigt haben, dass er erste Dominostein fällt, haben wir bewiesen, dass alles fallen wird.
Image by Denise Jans, shared on Unsplash

Zusammenfassung

Wir zeigen mit dem Induktionsanfang, dass der erste Dominostein fällt.

Mit dem Induktionsschritt zeigen wir ganz allgemein, dass ein fallender Dominostein (irgendwo, an \(k\)-ter Stelle, den nachfolgenden Dominostein (\(k+1)\) zum Fallen bringen wird.

Sobald beides gezeigt ist, wissen wir, dass die ganze Reihe von Dominosteinen fallen wird, bis in die Unendlichkeit, sofern nötig!

Als ich diese Methode das erste Mal hörte, habe ich mich gefragt, warum der Induktionsschritt alleine nicht ausreicht. Der Induktionsanfang erschien mir unnötig.

Nun, mit den Dominosteinen ist das einfach erklärt: Wenn wir bewiesen haben, dass ein fallender Dominostein den nächsten Dominostein zum Fallen bringen wird, haben wir noch nicht bewiesen, dass die ganze Reihe fallen wird. Es könnte ja sein, dass der erste Dominostein nicht fällt und damit die potenziell mögliche Kettenreaktion gar nie anfängt! Bevor wir den ersten Stein anstossen, passiert ja nichts, obwohl es passieren könnte. Genau aus diesem Grund müssen wir den Induktionsanfang auch zeigen.

Beispiel

Zeige mit Hilfe der vollständigen Induktion, dass der Trick von Gauss für die Summe der natürlichen Zahlen von 1 bis \(n\) gilt: \[ s_n = \frac{n \cdot (n+1)}{2} \] Anmerkung: Der kleine Gauss soll diese Formel in der Primarschule entwickelt haben, um die Summe der Zahlen von 1 bis 60 zu berechnen. 😆

Die Formel \(s_n = \frac{n \cdot (n+1)}{2}\) ist die Behauptung, die wir zu beweisen haben. Beim Induktionsanfang rechnen wir konkret nach, ob sie für das erste Glied schon erfüllt ist, d.h. ob die Summe von 1 bis 1 durch dir Formel korrekterweise 1 ergibt. Dazu setzen wir \(n=1\) in die Formel ein: \[ s_1 = \frac{1 \cdot (1+1)}{2} = \frac{1 \cdot 2}{2} = 1 \; \unicode{x2714} \] Soweit stimmt die Behauptung. Jetzt formulieren wir den Induktionsschritt. Wir machen die Annahme, dass die Formel für \(k\) gilt: \[ s_k = \frac{k \cdot (k+1)}{2} \; (\unicode{x2714}) \] Wir berechnen aufgrund dieser Annahme das nächste Glied: \[ s_{k+1} = s_k + (k+1) \] Weil wir die Annahme getroffen haben, dürfen wir die Formel für \(k\) einsetzen, denn sie gilt ja (Annahme): \[ s_{k+1} = \frac{k \cdot (k+1)}{2} + (k+1) \] Wir bringen die rechte Seite auf einen Bruch: \[ s_{k+1} = \frac{k \cdot (k+1) + 2 \cdot (k+1)}{2} \] Im Zähler können wir \((k+1)\) ausklammern \[ s_{k+1} = \frac{(k+1) \cdot (k + 2)}{2} \] Jetzt braucht es ein bisschen Voraussicht, denn wir formulieren \((k+2)\) um in \(((k+1)+1)\): \[ s_{k+1} = \frac{(k+1) \cdot ((k+1) + 1)}{2} \] Jetzt haben wir die ursprüngliche Formel wieder gefunden, einfach mit \((k+1)\) eingesetzt, statt \(k\). Vergleiche nochmals die ursprüngliche Formel: \[ s_k = \frac{k \cdot (k + 1)}{2} \] \[ s_n = \frac{n \cdot (n + 1)}{2} \] Das war die Formel, die wir zu beweisen hatten. Sie gilt offenbar für \((k+1)\), unter der Annahme, dass sie für \(k\) gilt. Das ist der Induktionsschritt! Damit ist die Behauptung bewiesen, denn sie gilt für \(s_1\) und für \(s_{k+1}\), wenn \(s_k\) gilt, d.h. sie gilt für \(s_2\), wenn sie für \(s_1\) gilt. Damit gilt sie dann auch für \(s_3\) und damit auch für \(s_4\) usw.

Beispiel

Zeige, dass die Folge \((a_n)\) Glieder hat, die durch 5 teilbar sind: \[ a_n = 12^n – 7^n \]

Wir machen den Induktionsanfang, d.h. rechnen einfach nach, ob \(a_1\) durch 5 teilbar ist: \[ a_1 = 12^1 – 7^1 = 12-7 = 5 \; \unicode{x2714} \] Tatsächlich ist das erfüllt für \(a_1\). Gehen wir zum Induktionsschritt und zeigen, dass unter der Annahme, dass \(a_k\) durch 5 teilbar ist, wir mit \(a_{k+1} \) eine Zahl kriegen, die auch durch 5 teilbar ist. Annahme: \(a_k\) ist durch 5 teilbar: \[ a_k = 12^k – 7^k \; (\unicode{x2714})\] Für das nächste Glied gilt (Formel): \[ a_{k+1} = 12^{k+1} – 7^{k+1} \] Mit Hilfe der Regeln für die Multiplikation von Potenzen können wir schreiben: \[ a_{k+1} = 12 \cdot 12^k – 7 \cdot 7^k \] Jetzt greifen wir ein bisschen in die Trickkiste: Wir subtrahieren den Term \(12 \cdot 7^k\) und addieren ihn wieder…das macht auf den ersten Blick keinen Sinn, aber dann werden wir die beiden Terme voneinander trennen. \[ a_{k+1} = 12 \cdot 12^k \;\;\;- 12 \cdot 7^k + 12 \cdot 7^k \;\;\; – 7 \cdot 7^k \] \[ a_{k+1} = (12 \cdot 12^k – 12 \cdot 7^k) \;\; + \;\; (12 \cdot 7^k – 7 \cdot 7^k) \] Jetzt können wir vorne \(12\) ausklammern und hinten geht es mit \(7^k\): \[ a_{k+1} = 12 \cdot (12^k – 7^k) \;\; + \;\; 7^k \cdot (12 – 7) \] Das war auch die Motivation, den Term \(12 \cdot 7^k\) einzuführen. Der Trick bestand darin, das Ausklammern hinzukriegen. Wir vereinfachen und ersetzen \(12^k – 7^k\) mit der Formel: \[ a_{k+1} = 12 \cdot a_k \; + \; 7^k \cdot 5 \]

Jetzt müssen wir zeigen, dass \(a_{k+1}\) durch 5 teilbar ist.

Wir haben die Annahme gemacht, dass \(a_k\) durch 5 teilbar ist, d.h. der linke Summand ist das 12-fache einer 5er-Zahl und somit durch 5 teilbar.

Der rechte Summand ist auch durch 5 teilbar und somit ist die Summe \(a_{k+1}\) durch 5 teilbar. Der Induktionsschritt ist damit bewiesen.

Wenn also \(a_1\) durch 5 teilbar ist (Induktionsanfang) und wir mit dem bewiesenen Induktionsschritt die “durch 5 teilbar”-Eigenschaft von einem durch 5-teilbaren Glied auf das nachfolgende Glied übertragen können, dann ist \(a_2\) eine 5er-Zahl, weil \(a_1\) eine war. Damit wird auch \(a_3\) eine 5er-Zahl und somit auch \(a_4\) usw.

Lernziele

  • Du kennst die zwei Bestandteile der vollständigen Induktion (Induktionsanfang und Induktionsschritt) und weisst, dass beim Induktionsschritt du eine Annahme triffst, woraus du schliesst, dass die Behauptung für das nächste Glied gilt.

  • Du kannst in eigenen Worten die Beweismethode der vollständigen Induktion beschreiben und sie an einfachen Beispielen anwenden.

Weitere Links

Folgen

Reihen

Vollständige Induktion (Wikipedia)

Feedback

Post Feedback Form

Autor dieses Artikels:

David John Brunner

Lehrer für Physik und Mathematik | Mehr erfahren

Kontakt

publiziert:

überarbeitet:

publiziert:

überarbeitet:

Frage oder Kommentar?

Frage/Kommentar?

Schreib deine Frage / Kommentar hier unten rein. Ich werde sie beantworten.

Schreibe einen Kommentar

Inhalt

GRATIS Scripts und Formelsammlungen
zur Übersicht
Praktische Hacks lernen…
…im Hacker-Club!
Übergeordnetes Thema:

    • Folgen
    Weitere Artikel zu diesem Thema:

      • Geometrische Folgen (GF)

      • Rekursive Definition

      • Explizite Definition

      • Arithmetische Folgen (AF)