Beweis durch vollständige Induktion

Der Induktionsbeweis gehört zu den ersten Beweismethoden, die man im Informatik-Studium lernt. Er beweist eine Aussage für alle natürlichen Zahlen mit nur zwei endlichen Schritten. Der Beweis beruht auf der Induktionseigenschaft der natürlichen Zahlen¹.

$$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$$

für alle $n \in \mathbb{N}$. Das Summenzeichen ist nur eine Kurzschreibweise für $1 + 2 + 3 + \dots + n$.

Herleitung

Schreibt man die Summe $S$ einmal vorwärts und einmal rückwärts untereinander, ergibt jedes Paar $n + 1$:

$$\begin{aligned} S &= 1 + 2 + \dots + (n-1) + n \\ S &= n + (n-1) + \dots + 2 + 1 \\ 2S &= (n+1) + (n+1) + \dots + (n+1) \end{aligned}$$

Das sind $n$ Summanden, jeder gleich $n + 1$:

$$2S = n(n+1)$$

Daraus folgt:

$$S = \frac{n(n+1)}{2}$$

Video²: „Die Vermessung der Welt - Der junge Gauß in der Schule“ von Das Bergische Bärchen auf YouTube.

Aufbau des Beweises

Grundlagen

Der Beweis gliedert sich im Grunde in fünf Schritte:

• Induktionsanfang
  • Wir zeigen, dass die Aussage für den kleinsten Fall stimmt.
• Induktionsvoraussetzung
  • Wir nehmen an, dass die Aussage für ein beliebiges $n$ gilt.
• Induktionsschritt
  • Wir zeigen, dass die Aussage dann auch für $n + 1$ gilt.
• Induktionsbehauptung
  • Das ist die Aussage, die wir für $n + 1$ zeigen wollen.
• Induktionsbeweis
  • Wir rechnen die Behauptung mit Hilfe der Voraussetzung nach.

In manchen Büchern gehören die Behauptung und der Beweis zum Induktionsschritt. Hier trennen wir sie, damit man die einzelnen Schritte besser sieht.

Der Beweis

Induktionsanfang

Im Induktionsanfang schauen wir, ob die Formel für den kleinsten Fall stimmt. Das ist hier $n = 1$. Zur Sicherheit rechnen wir auch $n = 2$ und $n = 3$ nach.

Für $n = 1$:

$$1 = \frac{1 \cdot (1+1)}{2} \;\Leftrightarrow\; 1 = \frac{2}{2} \;\Leftrightarrow\; 1 = 1$$

Für $n = 2$:

$$1 + 2 = \frac{2 \cdot (2+1)}{2} \;\Leftrightarrow\; 3 = \frac{6}{2} \;\Leftrightarrow\; 3 = 3$$

Für $n = 3$:

$$1 + 2 + 3 = \frac{3 \cdot (3+1)}{2} \;\Leftrightarrow\; 6 = \frac{12}{2} \;\Leftrightarrow\; 6 = 6$$

In allen drei Fällen sind beide Seiten gleich. Für den Beweis reicht eigentlich schon $n = 1$. Die anderen beiden Fälle zeigen nur, dass die Formel auch weiter stimmt.

Induktionsvoraussetzung

Jetzt nehmen wir an, dass die Formel für ein beliebiges $n$ stimmt. Das müssen wir nicht beweisen, wir setzen es einfach voraus:

$$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$$

Mit dieser Annahme arbeiten wir im nächsten Schritt weiter.

Induktionsschritt

Jetzt wollen wir zeigen, dass die Formel dann auch für den nächsten Wert $n + 1$ stimmt. Dazu addieren wir auf beiden Seiten der Voraussetzung $n + 1$:

$$\sum_{i=1}^{n} i + (n+1) = \frac{n(n+1)}{2} + (n+1)$$

Induktionsbehauptung

Wenn wir in der Formel überall $n + 1$ statt $n$ einsetzen, bekommen wir die Behauptung. Das ist genau das, was wir zeigen wollen:

$$\sum_{i=1}^{n+1} i = \frac{(n+1)\left((n+1)+1\right)}{2} = \frac{(n+1)(n+2)}{2}$$

Induktionsbeweis

Jetzt müssen wir nur noch zeigen, dass die rechte Seite aus dem Induktionsschritt gleich der rechten Seite der Behauptung ist. Dafür klammern wir $n + 1$ aus und fassen zusammen:

$$\begin{aligned} \frac{n(n+1)}{2} + (n+1) &= \frac{n(n+1)}{2} + \frac{2(n+1)}{2} \\ &= \frac{n(n+1) + 2(n+1)}{2} \\ &= \frac{(n+1)(n+2)}{2} \end{aligned}$$

Das ist genau die rechte Seite der Behauptung. Damit gilt die Formel für $n + 1$, wenn sie für $n$ gilt. Zusammen mit dem Induktionsanfang stimmt sie also für alle $n \in \mathbb{N}$.

Weiteres Beispiel: Ungerade Quadratzahlen

Hier ist wieder eine Summe, aber diesmal mit Quadraten. Wir zeigen: Die Summe der ungeraden Quadratzahlen bis $(2n-1)^2$ ist

$$1^2 + 3^2 + 5^2 + \dots + (2n-1)^2 = \sum_{k=1}^{n} (2k-1)^2 = \frac{n(2n-1)(2n+1)}{3}$$

Induktionsanfang: Für $n = 1$ ist die Summe nur $1^2 = 1$. Die Formel liefert

$$\frac{1 \cdot (2 \cdot 1 - 1)(2 \cdot 1 + 1)}{3} = \frac{1 \cdot 1 \cdot 3}{3} = 1$$

Das stimmt. Zur Probe noch $n = 2$ und $n = 3$:

$$\begin{aligned} 1^2 + 3^2 = 10 &= \frac{2 \cdot 3 \cdot 5}{3} \\ 1^2 + 3^2 + 5^2 = 35 &= \frac{3 \cdot 5 \cdot 7}{3} \end{aligned}$$

Induktionsvoraussetzung: Wir nehmen an, dass die Formel für ein beliebiges $n$ gilt:

$$\sum_{k=1}^{n} (2k-1)^2 = \frac{n(2n-1)(2n+1)}{3}$$

Induktionsschritt: Der nächste Summand ist $(2(n+1)-1)^2 = (2n+1)^2$. Den addieren wir auf beiden Seiten der Voraussetzung:

$$\sum_{k=1}^{n} (2k-1)^2 + (2n+1)^2 = \frac{n(2n-1)(2n+1)}{3} + (2n+1)^2$$

Induktionsbehauptung: Wenn wir $n + 1$ statt $n$ einsetzen, wollen wir zeigen:

$$\sum_{k=1}^{n+1} (2k-1)^2 = \frac{(n+1)(2n+1)(2n+3)}{3}$$

Induktionsbeweis: Wir klammern $(2n+1)$ aus und fassen zusammen:

$$\begin{aligned} \frac{n(2n-1)(2n+1)}{3} + (2n+1)^2 &= \frac{(2n+1)\left(n(2n-1) + 3(2n+1)\right)}{3} \\ &= \frac{(2n+1)(2n^2 + 5n + 3)}{3} \\ &= \frac{(2n+1)(n+1)(2n+3)}{3} \end{aligned}$$

Im letzten Schritt haben wir $2n^2 + 5n + 3 = (n+1)(2n+3)$ benutzt. Das ist genau die rechte Seite der Behauptung.

Warum ist das ein Beweis?

Wir haben nur den Anfang und den Schritt gezeigt und nicht jeden Fall einzeln nachgerechnet. Trotzdem reicht das, denn man kann es sich wie bei Dominosteinen vorstellen:

• Der Induktionsanfang wirft den ersten Stein um. Die Aussage stimmt für $n = 1$.
• Der Induktionsschritt sagt, dass jeder Stein den nächsten umwirft. Wenn die Aussage für $n$ stimmt, dann auch für $n + 1$.

Aus $n = 1$ folgt $n = 2$, daraus $n = 3$ und immer so weiter. Jede natürliche Zahl kommt irgendwann dran, weil man bei $1$ anfängt und immer nur um $1$ weiterzählt. Das ist die Induktionseigenschaft der natürlichen Zahlen von oben¹. Ohne den Anfang fällt kein Stein um und ohne den Schritt bricht die Kette irgendwo ab. Deswegen braucht man immer beides.

Titelbild³: Photo by Gabby K from Pexels.

Footnotes

1. https://de.wikipedia.org/wiki/Peano-Axiome (abgerufen am 01.10.2026) ↩ ↩²

2. https://www.youtube.com/watch?v=0QKB3i2tHNA (abgerufen am 01.10.2026) ↩

3. https://www.pexels.com/de-de/foto/text-6238068/ (abgerufen am 27.09.2026) ↩