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

Man beweise mittels vollständiger Induktion:
$\sum _{j=0}^{n}j2^{j}=2^{n+1}(n-1)+2\quad (n\geq 0)$

Beweis

(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.