Completing simplification step when solving a recurrence I am trying to understand a simplification step in one of the recurrence examples solved by repeated substitution in a book of algorithms problems I found on Github. I am using it for extra practice in solving recurrences. Anyways, here's the step I am stuck on:
I don't understand how to get from this:
$$3^{i-1}(3T(n-i)+2) + 2\sum_{j=0}^{i-2}3^j$$
To this:
$$3^iT(n-i)+2\sum_{j=0}^{i-1}3^j$$
The part I am particularly confused about is how the summation at the end of the recurrence changes from the first part above to the second. I don't understand how the upper limit in the summation changes from $i-2$ to $i-1$. I imagine I am forgetting something simple about how summations work. Any help is appreciated. I also appreciate excruciatingly detailed steps in showing the algebra or simplification math, if it's not too much trouble. This is often how I get stuck; when a simple step is omitted for brevity.  
 A: $$
3^i T(n-i) +2\cdot 3^{i-1}+2\sum_{j=0}^{i-2}3^j
$$
The last two terms are seen as
$$
2\sum_{j=0}^{i-1}3^j = 2\sum_{j=0}^{i-2}3^j + 2\cdot3^{i-1}
$$
$$
\sum_{j=1}^{3} a^j = a^1 + a^2 + a^3
$$ if I add $a^4$ to the mix its just the same as going from 1 to 4 in the summation. I think you are over thinking the manipulation as I first did ;).
A: You have a typo in the problem as stated:  The summand should be $3^j$, not $3^i$.  If you summand $3^i$ is really what you meant, then the quality indeed does not hold.
Assuming it is $3^j$:
Lop off the last item in the second sum:
$$
2\sum_{j=0}^{i-1}3^j =2\sum_{j=0}^{i-2}3^j + 2\cdot 3^{i-1}
$$
Then the simplification of the equality becomes trivial.
And by the way, if the 
A: So first we can distribute the $3^{i-1}$
$$
  3^{i-1}(3T(n-i)+2) + 2\sum_{j=0}^{i-2}3^i \\
  3^iT(n-i)+2\cdot3^{i-1} + 2\sum_{j=0}^{i-2}3^i
$$
Now if we write out the terms of that summation:
$$
 2\sum_{j=0}^{i-2}3^i = 2\cdot3^0 + 2\cdot3^1 +\dotsb + 2\cdot3^{i-2}  
$$
It looks like they just tacked that $2\cdot3^{i-1}$ onto the end of the summation:
$$
  3^iT(n-i)+2\cdot3^{i-1} + 2\sum_{j=0}^{i-2}3^i \\
  3^iT(n-i) + 2\sum_{j=0}^{i-2}3^i +2\cdot3^{i-1} \\
  3^iT(n-i) + \Big(2\cdot3^0 + 2\cdot3^1 +\dotsb + 2\cdot3^{i-2}\Big) +2\cdot3^{i-1} \\
  3^iT(n-i)+ 2\sum_{j=0}^{i-1}3^i \\
$$
A: $$3^{i-1}\color{green}(3T(n-i)+2\color{green}) + 2\sum_{j=0}^{i-2}3^i$$
$$\color{green}{3^{i-1}3}T(n-i)+3^{i-1}\color{green}2 + \color{green}2\sum_{j=0}^{i-2}3^i$$
$$3^iT(n-i) + 2(\color{green}{3^{i-1}+\sum_{j=0}^{i-2}3^i})$$
$$3^iT(n-i) + 2\sum_{j=0}^{i-1}3^i$$
