Gaußsche Summenformel

Behauptung:

$$\sum_{k=1}^n k = 1+2+3+\dots+n = \frac{n(n+1)}{2} \quad\text{fuer } \quad (n\geq 1)$$



Beweis:

Induktionsanfang: n = 1

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

Induktionsschritt: A(n) => A(n+1)

Angenommen, die Behauptung gilt für alle natürlichen Zahlen 1 … n. Dann soll sie auch für n+1 gelten. Wir müssen also, mit Hilfe der Voraussetzung, zeigen, daß:

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

Wir beginnen damit, dass wir den (n+1)ten Summanden aus dem Summenzeichen ziehen:

$$\sum_{k=1}^{n+1} k = \sum_{k=1}^{n} k + (n+1)$$

Nun können wir die Summe durch den Bruch aus der Behauptung ersetzen, denn unsere Induktionsvoraussetzung ist ja, dass beides das gleiche ist. Dies ist also die wichtige Stelle im Beweis, an der die Induktionsvoraussetzung benutzt wird:

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

Auf den Hauptnenner bringen:

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

Ausmultiplizieren und zusammenfassen:

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

Und dies ist was zu zeigen war.

Weiterlesen: 2n³ + 3n² + n ist durch 6 teilbar