Die vollständige Induktion ist ein Beweisverfahren, das angewendet wird, um zu beweisen, dass eine Aussage, die von einer natürlichen Zahl abhängt, für alle \(n \ge n_o\) gilt, wobei \(n_0 \in \mathbb{N}_0\). Wir schreiben \(A(n)\) für unsere Aussage in Abhängigkeit von \(n \in \mathbb{N}_0\).
Vorgehensweise:
1.) Induktionsanker/Induktionsanfang (kurz: IA):
Im Induktionsanker zeigen wir, dass \(A(n_0)\) wahr ist, wobei wir \(n_0 \in \mathbb{N_0}\) so klein wie möglich wählen. Meistens ist dies die Zahl 0 oder 1.
2.) Induktionsvoraussetzung (kurz: IV):
Hier setzen wir voraus, dass \(A(n)\) für ein festes, aber beliebiges \(n \in N\) gilt, wobei \(N :=\{m \in \mathbb{N} \ \vert \ m \ge n_0\} \). Meist schreiben wir sowas wie: „Für ein festes, aber beliebiges \(n \in N\) gilt: \(A(n)\)“, wobei wir für \(A(n)\) die Aussage hinschreiben.
Achtung:
Ein häufiger Fehler hierbei ist die folgende Formulierung: „Für \(n \in N\) gilt: \(A(n)\)“
Dort wird vorausgesetzt, dass unsere Aussage für alle \(n \in N\) wahr ist, womit wir uns die Induktion sparen könnten. Wir setzen in der Induktionsvoraussetzung lediglich voraus, dass ein \(n \in N\) die Aussage erfüllt!
3.) Induktionsschritt/Induktionsschluss (kurz: IS)
Im dritten und letzten Schritt findet die eigentliche Arbeit der Induktion statt. Wir möchten hier zeigen, dass, wenn die Aussage für unser festes, aber beliebiges \(n \in N\) wahr ist, sie auch für \(n+1\) gilt.
Kurz: \(A(n) \Rightarrow A(n+1)\)
Manchmal (aber selten) kommt es auch vor, dass wir zusätzlich den Induktionsanker verwenden können.
Zusammenfassung der Schritte:
Wir zeigen, dass \(A(n)\) für ein \(n_0 \in \mathbb{N}_0\) gilt (IA), setzen voraus, dass die Aussage für ein festes, aber beliebiges \(n \in N\) wahr ist (IV), um letztendlich im Induktionsschritt (IS) zu zeigen, dass die Eigenschaft der Aussage dann auch für \(n+1\) erfüllt ist. Somit ist \(A(n)\) für alle \(n \ge n_0\) wahr.
Idee „anschaulich“: \(\underbrace{A(n_0)}_{IA} \overset{IS}{\Rightarrow} A(n_0+1) \overset{IS}{\Rightarrow} A(n_0+2) \overset{IS}{\Rightarrow} \ldots \)
Damit die Vorgehensweise klarer wird, wird die Induktion an einem Beispiel erläutert.
Beispiel: Gaußsche Summenformel
Das wohl typischste Beispiel für die Anwendung der vollständigen Induktion ist die Gaußsche Summenformel, womit an dieser Stelle die Geschichte des kleinen Gauß erwähnt sei:
Der kleine Gauß sitzt mit seinen Mitschülern/Mitschülerinnen im Mathematikunterricht. Sie bekommen von ihre Lehrer folgende Aufgabe gestellt: „Berechnet die Summe der Zahlen von 1 bis 100!“
Der Lehrer, stark im Glauben er könne sich nun eine lange Auszeit gönnen, lehnt sich zurück und lässt die Schüler/innen rechnen. Alle beginnen die Zahlen mühsam zu addieren und schreiben ihre Zwischenschritte auf Schreibtafeln. Alle? Nein! Der kleine Gauß sitzt ruhig auf seinem Stuhl und denkt nach:
$$\begin{aligned} 1+100&=101 \\ 2+99 &= 101 \\ 3+98 &=101 \\ \quad &\vdots \\ 49+52 &=101 \\ 50+51 &=101 \end{aligned}$$
Er stellt fest, dass er durch schlaues Addieren der Summanden 50-mal die Zahl 101 erhält.
Es gilt:
$$\overset{100}{\underset{k=1}{\sum}} k = 50 \cdot 101 =5050$$
Natürlich kann man solch eine Summe nicht nur geschickt von 1 bis 100 ausrechnen, sondern bis zu einem beliebigen \(n \in \mathbb{N}\).
Es gilt:
$$\overset{n}{\underset{k=1}{\sum}}k= \frac{n \cdot (n+1)}{2} $$
Diese Aussage bezeichnen wir mit \(A(n)\).
Wir überprüfen, ob \(A(n)\) tatsächlich für \(n=100\) gilt:
$$\overset{100}{\underset{k=1}{\sum}}k= \frac{100 \cdot 101}{2}=\frac{50 \cdot 101}{1}=5050 $$
Woher wissen wir aber nun, dass dies nicht nur Zufall war? Ein Glücktreffer. Es könnte ja sein, dass die Aussage für \(n=100\) gilt, jedoch für \(n=101\) nicht. An dieser Stelle kommt die vollständige Induktion ins Spiel! Mit ihrer Hilfe beweisen wir, dass \(A(n)\) für alle natürlichen Zahlen \(n\) gilt.
Beweis:
Induktionsanker:
Sei \(n_0=1\).
Es gilt:
$$\overset{1}{\underset{k=1}{\sum}}k = 1 = \frac{1 \cdot (1+1)}{1}$$
Induktionsvoraussetzung:
Für ein festes, aber beliebiges \(n \in \mathbb{N}\) gilt:
$$\overset{n}{\underset{k=1}{\sum}}k= \frac{n \cdot (n+1)}{2} $$
Induktionsschritt:
$$\begin{aligned} \overset{n+1}{\underset{k=1}{\sum}}k &= \overset{n}{\underset{k=1}{\sum}}k+(n+1) \\ &\overset{IV}{=} \frac{n \cdot (n+1)}{2} + (n+1) \\ &= \frac{n \cdot (n+1)}{2} + \frac{2 \cdot (n+1)}{2} \\ &= \frac{n \cdot (n+1)+2 \cdot (n+1)}{2} \\ &=\frac{(n+2) \cdot (n+1)}{2} \\ &= \frac{(n+1) \cdot ((n+1)+1)}{2} \end{aligned}$$
Wir haben nun in wenigen Schritten gezeigt, dass \( A(n) \) für alle natürlichen Zahlen \(n \) gilt.
Wieso funktioniert die vollständige Induktion als Beweisverfahren überhaupt? Um diese Frage zu beantworten, beweisen wir folgende Aussage:
Gilt eine Aussage \(A(n_0)\) für ein \(n_0 \in \mathbb{N}_0\) und folgt aus der wahren Aussage \(A(n)\) mit \(n \in N \), dass \(A(n+1)\) ebenfalls gilt, so ist \(A(n)\) für alle \(n \in N\) wahr.
Beweis:
Addieren wir zu einem \(n_0 \in \mathbb{N}_0\) eine \(1\), so erhalten wir die darauffolgende natürliche Zahl \(n_0+1\). Wir können jede beliebig große natürliche Zahl \(n \ge n_0 \) erhalten indem wir entsprechend oft eine \(1\) addieren. Dies wird als Prinzip der vollständigen Induktion bezeichnet.
Nun wissen wir, dass \(A(n_0)\) für ein \(n_0 \in \mathbb{N}_0\) und \(„A(n) \ \text{wahr} \ \Rightarrow A(n+1) \ \text{wahr}“\) gilt. Um zu beweisen, dass die Aussage für eine beliebige natürliche Zahl aus \(N\) gilt, müssen wir also \(„A(n) \ \text{wahr} \ \Rightarrow A(n+1) \ \text{wahr}“\) entsprechend oft anwenden.
Somit gilt \(A(n)\) für alle \(n \in N\).
Beispiele für weitere Gleichungen, die mit Hilfe der vollständigen Induktion bewiesen werden können:
1.) Für \(n \in \mathbb{N}\) gilt:
$$\overset{n}{\underset{k=1}{\sum}}k^2 = \frac{n \cdot (n+1) \cdot (2n+1)}{6}$$
2.) Für \(n \in \mathbb{N}\) gilt der binomische Lehrsatz:
$$(x+y)^n=\overset{n}{\underset{k=1}{\sum}} \binom{n}{k} \cdot x^{n-k} \cdot y^k$$
