Beweise durch vollständige Induktion – Erklärung, Beispiele und Tipps

Lerne, wie man mit vollständiger Induktion mathematische Aussagen für alle natürlichen Zahlen beweist. Die vier Schritte – Induktionsanfang, -annahme, -schritt und -schluss – sind entscheidend. Möchtest du mehr über vollständige Induktion und Beispiele erfahren?

Inhaltsverzeichnis zum Thema Vollständige Induktion

Vollständige Induktion im Überblick

  • Die vollständige Induktion ist eine Methode für Beweise in der Mathematik.
  • Einsatz findet die vollständige Induktion bei Aussagen, die für alle natürlichen Zahlen gelten.

  • Ein Beweis mit vollständiger Induktion ist immer aus den gleichen vier Schritten aufgebaut:
    1. Induktionsanfang
    2. Induktionsannahme
    3. Induktionsschritt
    4. Induktionsschluss

Vollständige Induktion: Lernvideo

Quelle sofatutor.com

Quelle sofatutor.com

Vollständige Induktion einfach erklärt

Die vollständige Induktion ist eine Beweismethode in der Mathematik. Damit können Aussagen bewiesen werden, die für die Menge der natürlichen Zahlen gelten. Formal schreibt man:

A(n) gilt für alle n\in\mathbb{N}.

Die vier Schritte der vollständigen Induktion

Bewiesen werden soll die Aussage A(n) für alle n \in \mathbb{N}.

  1. Induktionsanfang: Die Aussage wird für eine beliebige Zahl, in der Regel für n=1 bzw. die kleinste Zahl, für die die Aussage gelten soll, bewiesen.
  2. Induktionsannahme (oder Induktionsvoraussetzung): Es wird angenommen, dass A(n) für ein n\in \mathbb{N} gilt.
  3. Induktionsschritt: Nun wird gezeigt, dass die Aussage A(n) auch für den Nachfolger von n gilt, also dass A(n+1) richtig ist.
    In diesem Schritt ist in der Regel am meisten zu tun: Mit mehr oder weniger aufwendigen Umformungen und Argumentationen wird die Aussage A(n+1) gezeigt. Dabei wird die Induktionsannahme verwendet, also dass A(n) bereits gilt.
  4. Induktionsschluss: Nun wird aus 1. bis 3. gefolgert, dass A(n) für alle n\in\mathbb{N} gilt.

Beispielaufgaben mit der vollständigen Induktion lösen

Im Folgenden schauen wir uns Aufgaben an, in denen Aussagen mit vollständiger Induktion bewiesen werden können.

Gaußsche Summenformel mit vollständiger Induktion

Wir möchten nun die Summenformel von Gauß beweisen. Diese lautet wie folgt:

A(n): \displaystyle \sum_{k=1}^n k =\dfrac{n\cdot (n+1)}{2}~​​ gilt für alle n\in\mathbb{N}.

Das bedeutet, dass die Summe aller Zahlen von 1 bis zu einer beliebigen Zahl n\in\mathbb{N} mit der Formel \frac{n\cdot(n+1)}{2} berechnet werden kann.

1. Induktionsanfang
Wir zeigen, dass die Formel für n=1 gilt:
\displaystyle \sum_{k=1}^1 k =1 = \frac{1\cdot (1+1)}{2}

Die Aussage A(1) stimmt also.

2. Induktionsannahme
Da die Aussage A(n) für n=1 gilt, ist anzunehmen, dass die Aussage A(n) für ein beliebiges n gilt.

3. Induktionsschritt
Nun zeigen wir, dass unter der Voraussetzung, dass A(n) gilt, auch A(n+1) gilt. Es muss also gezeigt werden, dass gilt:
\displaystyle \sum_{k=1}^{\mathbf{n+1}} k =\dfrac{(\mathbf{n+1})\cdot ((\mathbf{n+1})+1)}{2}​​

Es gilt:
\displaystyle \sum_{k=1}^{n+1} k = 1+2+\cdots+n+(n+1) = \left(\sum_{k=1}^{n} k\right) +(n+1)

Für die weitere Umformung können wir nun unsere Induktionsannahme verwenden, da wir ja schon wissen, dass
\displaystyle \sum_{k=1}^n k =\frac{n\cdot (n+1)}{2}​​ gilt.
Damit erhalten wir folgenden Ausdruck, den wir weiter umformen:
\begin{array}{rcll} \displaystyle \sum_{k=1}^{n+1} k = \left(\sum_{k=1}^{n} k\right) +(n+1) & = & \dfrac{n\cdot(n+1)}{2} + (n+1)&\mid\text{auf einen Nenner bringen} \\ & = & \dfrac{n\cdot(n+1)}{2} + \dfrac{2\cdot(n+1)}{2} & \\ & = & \dfrac{n\cdot(n+1)+2\cdot(n+1)}{2} &\mid (n+1)\text{ ausklammern} \\ & = & \dfrac{(n+1)\cdot(n+2)}{2} &\mid (n+2)\text{ umschreiben} \\ & = & \dfrac{(n+1)\cdot((n+1)+1)}{2} & \\ \end{array}

4. Induktionsschluss
In der letzten Zeile der Umformungsschritte steht nun genau, was gezeigt werden sollte, also die Aussage A(n+1):
\displaystyle \sum_{k=1}^{n+1} k =\frac{(n+1)\cdot ((n+1)+1)}{2}​​

Damit haben wir gezeigt, dass A(n) für alle n\in\mathbb{N} gilt.

Bernoullische Ungleichung mit vollständiger Induktion

Die bernoullische Ungleichung besagt, dass für jede natürliche Zahl n\geq0 und jede reelle Zahl x\geq -1 folgende Ungleichung gilt:
A(n): (1+x)^n\geq 1+n\cdot x

1. Induktionsanfang
Wir zeigen, dass die Formel für n=0 gilt:
A(0): (1+x)^0 = 1 \geq 1+0\cdot x

2. Induktionsannahme
Da die Aussage A(n) für n=0 gilt, ist anzunehmen, dass die Aussage A(n) für ein beliebiges n gilt, also:
A(n): (1+x)^n\geq 1+n\cdot x

3. Induktionsschritt
Nun zeigen wir, dass unter der Voraussetzung, dass A(n) gilt, auch A(n+1) gilt. Es muss also gezeigt werden, dass gilt:
A(n+1): (1+x)^{n+1}\geq 1+(n+1)\cdot x

Wir formen um und verwenden dabei die Induktionsannahme:

\begin{array}{rcll} (1+x)^{n+1}& = & (1+x)^n\cdot (1+x) &\mid\text{Induktionsannahme einsetzen}\\ & \geq & (1+n\cdot x)\cdot (1+x)&\mid\text{ausmultiplizieren} \\ & = & 1 + x+nx+nx^2 &\mid \text{letzten Term weglassen}\\ & \geq & 1 + x+nx &\mid \text{ausklammern}\\ & = & 1 + (n+1)\cdot x & \\ \end{array}

4. Induktionsschluss
In der letzten Zeile der Umformungsschritte steht nun genau, was gezeigt werden sollte.
A(n+1): (1+x)^{n+1}\geq 1 + (n+1)\cdot x

Damit haben wir gezeigt, dass gilt:
(1+x)^n\geq 1+n\cdot x für alle n\in\mathbb{N}_0

Häufig gestellte Fragen zum Thema Vollständige Induktion

Die vollständige Induktion ist eine Beweismethode, mit der mathematische Aussagen bewiesen werden können, die für alle natürlichen Zahlen gelten.

Ein Beweis mit vollständiger Induktion folgt den immer gleichen vier Schritten: Induktionsanfang, Induktionsannahme, Induktionsschritt, Induktionsschluss.

Die vollständige Induktion ist ein Beweisverfahren, mit dem Aussagen in der Mathematik bewiesen werden können, die für alle natürlichen Zahlen gelten. Formal geschrieben wird gezeigt: A(n) gilt für alle n\in\mathbb{N}.

Bei einer starken vollständigen Induktion wird der Induktionsanfang für mehrere Vorgänger ausgeführt.

Da in den reellen Zahlen der Nachfolger einer Zahl nicht eindeutig definiert ist, kann die vollständige Induktion für Aussagen, die in den reellen Zahlen gelten sollen, nicht angewendet werden. Der Induktionsschritt funktioniert dann nicht.

Super! Das Thema: kannst du schon! Teile deine Learnings und Fragen mit der Community!

Alle Artikel aus dem Fach Mathematik