Evaluating $\sum_{i=0}^{k-1} 4^i(i-1)$ for recurrence relation exercise I need help to solve the following sum:
$$\sum_{i=0}^{k-1} 4^i(i-1)$$
I'm doing some exercises about recurrence relations in algorithms and this sum came up. 

The exercise stands like:

$$T(n) = \frac {1}{2}n + 4T(\frac{n}{2} + 3)$$

And the result I get was:

$$ T(n) = 4^n T(\frac{n}{2^k}+3k)+[\sum_{i=0}^{k-1}\frac{4^in}{2^{i+1}}+4^i*3*(i-1)]$$

All of this is new to me, all the examples i saw online are way more different than this excercise 

Am I getting closer to an answer?


Note: No base case was given


Thanks in advance!


One way might be$$A=\sum _{ i=0 }^{ k-1 } 4^{ i }(i-1)=-1+{ 4 }^{ 2 }+{ 4 }^{ 3 }\cdot 2+{ 4 }^{ 4 }\cdot 3+...+{ 4 }^{ k-1 }\left( k-2 \right) \\ A+1={ 4 }^{ 2 }+{ 4 }^{ 3 }\cdot 2+{ 4 }^{ 4 }\cdot 3+...+{ 4 }^{ k-1 }\left( k-2 \right) \\ 4\left( A+1 \right) ={ 4 }^{ 3 }+{ 4 }^{ 4 }\cdot 2+{ 4 }^{ 5 }\cdot 3+...+{ 4 }^{ k }\left( k-2 \right) \\ \left( A+1 \right) -4\left( A+1 \right) ={ 4 }^{ 2 }+\left( { 4 }^{ 3 }\cdot 2-{ 4 }^{ 3 } \right) +\left( { 4 }^{ 4 }\cdot 3-{ 4 }^{ 4 }\cdot 2 \right) +...+\left( { 4 }^{ k-1 }\left( k-2 \right) -{ 4 }^{ k-1 }\left( k-3 \right)  \right) -{ 4 }^{ k }\left( k-2 \right) \\ -3\left( A+1 \right) ={ 4 }^{ 2 }+{ 4 }^{ 3 }+...+{ 4 }^{ k-1 }-{ 4 }^{ k }\left( k-2 \right) \\ -3\left( A+1 \right) =\frac { { 4 }^{ 2 }\left( 1-{ 4 }^{ k } \right)  }{ 1-4 } -{ 4 }^{ k }\left( k-2 \right) ={ 4 }^{ k }\left( \frac { 22 }{ 3 } -k \right) \\ A=\frac { { 4 }^{ k } }{ -3 } \left( \frac { 22 }{ 3 } -k \right) -1\\ $$
or finding a derivative of $\sum _{ i=0 }^{ n }{ { x }^{ n } } $
