$$T(n) =\begin{cases}5, & \text{if $n=1$} \\2T(n-1)+3n+1, & \text{if $n\geq 2$}\end{cases}$$
Now the answer is as such:
- $T(n)=5\cdot 2^{n-1}+\sum_{i=2}^n2^{n-i}(3i+1)$, which I certainly understand.
- $=(3n+6)2^{n-1}-3n-1-3\sum_{i=1}^{n-2}i\cdot 2^i=15\cdot 2^{n-1}-3n-7$, which throws me a big curve ball right immediately without any sense.
Could anyone explain to me the drastic transition algebraically?
A change of variable $j=n-i$ gives: \begin{align} T(n) &=5\cdot 2^{n-1}+\sum_{i=2}^n2^{n-i}(3i+1)\\ &=5\cdot 2^{n-1}+\sum_{j=0}^{n-2}2^j(3(n-j)+1)\\ &=5\cdot 2^{n-1}+(3n+1)\sum_{j=0}^{n-2}2^j-3\sum_{j=0}^{n-2}j2^j\\ &=5\cdot 2^{n-1}+(3n+1)(2^{n-1}-1)-3\sum_{j=0}^{n-2}j2^j\\ \end{align} Now you need: \begin{align} \sum_{i=0}^{n-1}ix^{i-1} &=\frac d{dx}\sum_{i=0}^{n-1}x^i\\ &=\frac d{dx}\frac{x^n-1}{x-1}\\ &=\frac{nx^{n-1}(x-1)-(x^n-1)}{(x-1)^2}\\ &=\frac{(n-1)x^n-nx^{n-1}+1}{(x-1)^2} \end{align} which for $x=2$ become: $$\sum_{i=0}^{n-1}i2^{i-1}=(n-1)2^n-n2^{n-1}+1$$