Vollständige Induktion

Beweise mit vollst. Induktion, dass die Summe der ersten n Zahlen $\sum \limits_{i=1}^n i = \frac{n(n+1)}{2}$ ist.

Induktionsanfang:

Für n=1: Die Summe der ersten 1 Zahlen ist 1. Prüfen wir die Formel: $\frac{1 \cdot (1+1)}{2} = \frac{2}{2} = 1$. Also für n=1 gilt die Formel.

Annahme: die Formel gilt für ein beliebiges n. Also gilt: $\sum \limits_{i=1}^n i = \frac{n(n+1)}{2}$

Wenn wir die Summe der ersten n+1 Zahlen ($\sum \limits_{i=1}^{n+1} i $) haben wollen, dann kann man ja sagen, das ist die Summe der ersten n Zahlen PLUS n+1.

Also: $\sum \limits_{i=1}^{n+1} i   \  = \   \sum \limits_{i=1}^{n} i \  + (n+1)$

Auf der rechten Seite der Gleichung setzen wir nun für $\sum \limits_{i=1}^n i $ die Formel der Annahme ein.

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

und formen die Rechte Seite um. Es wird versucht, die Form der Formel der Annahme zu erhalten, nur dass anstatt "n" dann "n+1" da steht, also im Zähler (n+1)((n+1)+1)  bzw. (n+1)(n+2). Wenn wir das ausmultiplizieren erhalten wir $(n+1)(n+2) = n^2 + n + 2n + 2$

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

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

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

$$\sum \limits_{i=1}^{n+1} i   \  = \   \frac{n^2 + n \ + \  2n+2}{2} \ \ \ (*)$$

Hier kommt jetzt der Trick bei der Sache. Wir wollten erreichen, dass im Zähler rechts der Ausdruck (n+1)((n+1)+1) also (n+1)(n+2) steht.  $(n+1)(n+2) = n^2 + n + 2n + 2$.  Aber das steht ja schon im Ausdruck (*) auf der rechten Seite im Zähler da!

Die Formel in der Annahme gilt also auch für n+1 (und dies nennt man den "Induktionsschluss"):

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

Zusammenfassung:

Wir haben ausgerechnet, dass die Formel (a) für n=1 gilt. Dann haben wir bewiesen, dass (b) wenn sie für n gilt, dass sie dann auch für n+1 gilt.

Daraus folgern wir, weil sie (wegen (a)) für n=1 gilt, dann gilt sie (wegen (b)) auch für n=2. Und weil sie für n=2 gilt, dann gilt sie (wegen (b)) auch für n=3. Und weil sie für n=3 gilt, dann gilt sie (wegen (b)) auch für n=4. Und wenn wir das immer so weitermachen, haben wir das für alle $n \in \mathbb{N}$.