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

Aus VoWi
Zur Navigation springen Zur Suche springen

Man beweise mittels Vollständiger Induktion:

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


Lösung[Bearbeiten]

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: \quad \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: \quad \sum_{j=2}^{n} j(j-1) = \frac{(n-1)n(n+1)}{3}


Induktionsbehauptung:


n+1: \quad \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: \quad \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 + 3n)}{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}