Vollständige Induktion

Vollständige Induktion 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.

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.

Alternative Begriffe: Beweis durch Induktion, Beweis durch vollständige Induktion, Induktionsbeweis, mathematische Induktion, Prinzip der vollständigen Induktion.