Multiplikatoren

$\text{f}_1=1; \text{ f}_n=2\text{f}_{n-1} + n,\ n \geq 2$;

$$\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\: \left. \parbox{10em}{... ...text{f}_1 + \sum\limits_{i=0}^{n-2}2^i(n-i) = 2^{n+1} - n - 2$$

Addieren aller Gleichungen:

$$\text{f}_n=2^{n-1} + \sum_{i=0}^{n-2}2^i(n-i) = \underbrac... ...-2}2^i}_{(2)} - \underbrace{\sum_{i=0}^{n-2}i\cdot 2^i}_{(3)}$$

(2) (Geometrische Reihe): $n\sum\limits_{i=0}^{n-2}2^i = n (2^{n-1}-1)$
(3) (Substitution: n-2=k):

$$\begin{split} \sum_{i=0}^{k}ix^i &= \sum_{i=1}^{k}ix^i \te... ...t)\\ &= \frac{kx^{k+2}-x^{k+1}(k+1)+x}{(x-1)^2}\\ \end{split}$$

Einsetzen von k=n-2 und x=2:

$$\leadsto \sum_{i=0}^{n-2}i2^i = 2^n(n-2)-2^{n-1}(n-1)+2 = 2^nn-2^{n+1}-2^{n-1}n+2^{n-1}+2$$

(2)-(3):

$$\begin{split} n\sum_{i=0}^{n-2}2^i - \sum_{i=0}^{n-2}i2^i ... ...{n-1}n-2^{n-1}-2\\ &=2^{n-1}(2n-1)-2^n(n-2)-n-2\\ \end{split}$$

(1)+(2)-(3):

$$\begin{split} 2^{n-1} + n\sum_{i=0}^{n-2}2^i + \sum_{i=0}^{... ...1} + 2^{n-1}(2n-1)-2^n(n-2)-n-2\\ &=2^{n+1}-n-2\\ \end{split}$$