TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS13/Beispiel 66

Man beweise mittels Vollständiger Induktion:

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

Lösung

In den Materialien ganz unformal gelöst zu finden - als Hilfe weil man sich gerade am Anfang schwer tut :-)

Induktionsanfang : Der Induktionsanfang für $n = 2$ muss überprüft werden.

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

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

$2 = 2$

Induktionsvoraussetzung :

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

Induktionsbehauptung:

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

Induktionsschritt:

Zu zeigen ist, dass die Summe auch für $n + 1$ gültig ist.

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

Die Summer der linken Seite kann aufgespalten werden.

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

Unter Zuhilfenahme der Induktionsvoraussetzung kann auf der linken Seite die Summe ersetzt werden, denn wir nehmen an, dass sie für $n$ gültig ist.

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

Mit Äquivalenzumformungen der linken Seiten zeigen wir nun, dass sie gleich der rechten Seite ist.

Alles auf einen Nenner bringen.

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

Im Zähler kann man $(n + 1)$ herausheben.

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

Im Zähler kann man $n$ herausheben.

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

Die beiden Seiten sind gleich. Die Aussage über die Summe ist für $n + 1$ bewiesen.

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