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

Aus VoWi
Zur Navigation springen Zur Suche springen

Man beweise mittels vollständiger Induktion:

\sum_{j=0}^{n} j2^j = 2^{n+1}(n-1)+2 \qquad (n \geq 0)

Lösung von Weaver[Bearbeiten]

Induktionsanfang:

 n = 0

Zu zeigen ist also:

\sum_{j=0}^{0} j2^j = 2^{1}(-1)+2

0*1 = -2 + 2

0 = 0 \qquad q.e.d.

Induktionsvoraussetzung:

Diese entspricht der Angabe:

\sum_{j=0}^{n} j2^j = 2^{n+1}(n-1)+2

Induktionsbehauptung:

Die durch die Gleichung beschriebene Eigenschaft überträgt sich von n auf n+1:

\sum_{j=0}^{n+1} j2^j = 2^{n+2}(n)+2

Induktionsschritt:

Wir betrachten die Induktionsbehauptung:

\sum_{j=0}^{n+1} j2^j = 2^{n+2}(n)+2

Wir extrahieren den letzten Summanden (mit j = n+1) aus der Summe links:

(\sum_{j=0}^{n} j2^j)+(n+1)2^{n+1} = 2^{n+2}(n)+2

Wir setzen aus der Induktionsvoraussetzung für die übrig gebliebene Summe ein:

(2^{n+1}(n-1)+2)+(n+1)2^{n+1} = 2^{n+2}(n)+2

Wir subtrahieren auf beiden Seiten 2 und heben links 2^{n+1} heraus:

2^{n+1}(n-1+n+1) = 2^{n+2}(n)

Den resultierenden Faktor 2 aus dem Klammernausdruck 2n links verschieben wir in den Exponenten der Potenz (erhöhen ihn also um 1):

2^{n+2}n = 2^{n+2}n \qquad q.e.d.