Definition
Die vollständige Induktion ist eine mathematische Beweisführung. Meist soll damit gezeigt werden, dass eine Formel für alle natürlichen Zahlen (also 1, 2, 3, 4 usw.) gilt.
Alternative Begriffe: Beweis durch Induktion, Beweis durch vollständige Induktion, Induktionsbeweis, mathematische Induktion, Prinzip der vollständigen Induktion.
Beispiel
Es soll mit vollständiger Induktion gezeigt werden, dass die Gaußsche Summenformel gilt:
$$\sum_{i=1}^n i = \frac{n \cdot (n + 1)}{2}$$
Also z.B. für n = 4:
$$\sum_{i=1}^4 i = 1 + 2 + 3 + 4 = 10 = \frac{4 \cdot (4 + 1)}{2}$$
Die vollständige Induktion beginnt damit, die Formel für n = 1 zu zeigen:
Linke Seite der Formel: $\sum_{i=1}^1 i = 1$
Rechte Seite der Formel: $\frac{1 \cdot (1 + 1)}{2} = \frac{2}{2} = 1$
Für n = 1 stimmt die Formel also schon mal.
Anschließend setzt man voraus, dass die Formel allgemein für n gilt und zeigt, dass sie auch für "eins mehr", also n +1 gilt.
Linke Seite der Formel:
$$\sum_{i=1}^{n+1} i = \sum_{i=1}^n i + (n +1)$$
Setzt man nun für $\sum_{i=1}^n i = \frac{n \cdot (n + 1)}{2}$ – was ja für n gelten soll –, erhält man:
$$\frac{n \cdot (n + 1)}{2} + (n +1)$$
$$= \frac{n \cdot (n + 1)}{2} + \frac{2 \cdot (n +1)}{2}$$
$$= \frac{(n + 2) \cdot (n + 1)}{2}$$
Und das ist auch das, was auf der rechten Seite der Formel steht, wenn man dort (n + 1) für n einsetzt:
$$= \frac{(n + 1) \cdot (n + 1 + 1)}{2} = \frac{(n + 1) \cdot (n + 2)}{2}$$
Was für n = 1 gilt, gilt also auch für n = 1 + 1 = 2; und was für n = 2 gilt, gilt auch für n = 2 + 1 = 3 usw., also für alle n.
Fazit
- Die vollständige Induktion beweist Aussagen, die für alle ganzen Zahlen ab einem Startwert gelten sollen — meist natürliche Zahlen
- Schritt 1 — Induktionsanfang: Aussage für $n = 1$ (oder den Startwert) zeigen
- Schritt 2 — Induktionsschritt: Unter Annahme, die Aussage gilt für $n$ (Induktionshypothese), zeigen, dass sie auch für $n + 1$ gilt
- Die Gaußsche Summenformel lautet: $\sum_{i=1}^n i = \frac{n(n+1)}{2}$
Selbsttest: Vollständige Induktion
Aufgabe: Vollständige Induktion
Beweisen Sie mit vollständiger Induktion: $2^n > n$ für alle $n \in \mathbb{N}$.
Induktionsanfang ($n = 1$): $2^1 = 2 > 1$ ✓
Induktionshypothese (IH): Für ein beliebiges $n \geq 1$ gelte $2^n > n$.
Induktionsschritt ($n \to n+1$):
$2^{n+1} = 2 \cdot 2^n \stackrel{\text{IH}}{>} 2n$
Da $n \geq 1$ gilt: $2n = n + n \geq n + 1$
Also: $2^{n+1} > 2n \geq n + 1$ ✓
Da Induktionsanfang und Induktionsschritt gezeigt sind, gilt $2^n > n$ für alle $n \in \mathbb{N}$. ✓
Probe: $n = 3$: $2^3 = 8 > 3$ ✓ $n = 5$: $2^5 = 32 > 5$ ✓