TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 8

Aus VoWi
Wechseln zu: Navigation, Suche

Man beweise mittels vollständiger Induktion:

 \sum_{k=1}^{n} k5^k = \frac{5}{16}(n5^{n+1} - (n+1)5^n + 1) \qquad n \geq 1

Induktionsanfang:  n = 1 ergibt

Linke Seite:  1*5^1 = 5

Rechte Seite:  \frac{5}{16}(1*5^2 - 2*5^1 + 1) = \frac{5}{16}(16) = 5

OK.

Induktionsvorraussetzung: Es muss gezeigt werden, dass gilt:

 \sum_{k=1}^{n+1} k5^k = \frac{5}{16}((n+1)5^{n+1+1} - (n+1+1)5^{n+1} + 1)

(Alle n durch n+1 ersetzt)

Wir formen die rechte Seite weiter um, zwecks Vereinfachung:

 \frac{5}{16}(n*5^{n+2} + 5^{n+2} - n*5^{n+1} - 2*5^{n+1} + 1) =

Wir heben  5^n heraus!

 = \frac{5}{16}(5^n*(n*5^{2} + 5^{2} - n*{5} - 2*5) + 1) =

 = \frac{5}{16}(5^n*(25n + 25 - 5n - 10) + 1) =

 = \frac{5}{16}(5^n*(20n + 15) + 1)

Induktionsschluss: (Nachweis der Induktionsbehauptung)

Die rechte  (n+1)*5^{n+1} zu addieren. Wir vereinfachen diesen Addend:

 (n+1)*5^{n+1} = 5*(n+1)*5^{n}

Es soll sich ergeben:  \frac{5}{16}(5^n*(20n + 15) + 1)

 \frac{5}{16}(n5^{n+1} - (n+1)5^n + 1) + 5*(n+1)*5^{n} =

Da einigen der Übergang zum nächsten Schritt etwas unklar war, füge ich ein - zunächst wird der rechte Addend mit \frac{16}{16} multipliziert:

 \frac{5}{16}(n5^{n+1} - (n+1)5^n + 1) + \frac{16*5*(n+1)*5^{n}}{16} =

Praktischerweise ist im linken Addend schon 5 herausgehoben - da auch im rechten Addend 5 herausgehoben werden kann, kommen wir auf:

 = \frac{5}{16}*(n5^{n+1} - (n+1)5^n + 1 + 16(n+1)*5^{n} )=

 = \frac{5}{16}*(n5^{n+1} - (n+1)5^n + 1 + (16n+16)*5^{n} )=

Wiederum heben wir  5^n heraus und erhalten:

 = \frac{5}{16}*(5^n * (5n - n -1 + 16n+16) + 1 )=

 = \frac{5}{16}(5^n*(20n + 15) + 1)

Q.e.d.

(Siehe auch f.thread:36134 )