Completing simplification step when solving a recurrence

Question

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.

Answer 1

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 \\ $$

Answer 2

$$ 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 ;).

Answer 3

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

Answer 4

$$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$$