TU Wien Nav:Mathematik für Informatik (Buch)/1.1d

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 \quad (n \geq 0)

Beweis[Bearbeiten]

(i) Induktionsanfang

n = 0:
0*2^{0} = 2 * (-1) + 2
0 = 0

(ii) Induktionsschritt

Induktionvoraussetzung:

\sum_{j=0}^{n} j2^{j} = 2^{n+1}(n-1)+2, für (n \geq 0)

Induktionsbehauptung:

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

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

Einsetzen der rechten Seite der Induktionsvoraussetzung:

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

n2^{n+1}+2^{n+1}+n2^{n+1}-2^{n+1}+2 = 2^{n+2}n+2

2^{n+2}n+2 = 2^{n+2}n+2

Q.E.D.