Find a closed-form solution for the following recurrence $$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$$
