# Find closed formula by changing order of summation: $\sum_{i=1}^ni3^i$

Working on homework for a probability and computing class, but my ability to work with summations is rusty to say the least, so I suspect this is going to turn out pretty straightforward.

Problem asks to find a closed formula for $$\sum_{i=1}^ni3^i$$ by representing it as a double sum and changing the order of summation. I did that by following a hint from the instructor and came up with $$\sum_{k=1}^n\sum_{i=k}^n3^i,$$ but I'm not really sure what that accomplished. What's the next step? What am I looking for here?

Here is a rather detailed elaboration which might be useful.

We obtain \begin{align*} \color{blue}{\sum_{i=1}^ni3^i}&=\sum_{i=1}^n\left(\sum_{k=1}^i 1\right)3^i\tag{1}\\ &=\sum_{i=1}^n\sum_{k=1}^i 3^i =\sum_{1\leq k\leq i\leq n}3^i =\sum_{k=1}^n\sum_{i=k}^n3^i\tag{2}\\ &=\sum_{k=1}^n\sum_{i=0}^{n-k}3^{i+k}\tag{3}\\ &=\sum_{k=1}^n3^k\cdot\frac{3^{n-k+1}-1}{3-1}\tag{4}\\ &=\frac{1}{2}\sum_{k=1}^n\left(3^{n+1}-3^k\right)\tag{5}\\ &=\frac{n}{2}3^{n+1}-\frac{1}{2}\sum_{k=1}^n3^k\tag{6}\\ &=\frac{n}{2}3^{n+1}-\frac{1}{2}\cdot\left(\frac{3^{n+1}-1}{3-1}-1\right)\tag{7}\\ &=\frac{n}{2}3^{n+1}-\frac{1}{4}3^{n+1}+\frac{3}{4}\tag{8}\\ &\color{blue}{=\frac{n}{4}(2n-1)3^{n+1}+\frac{3}{4}}\tag{9} \end{align*}

Comment:

• In (1) we represent the factor $i$ as sum.

• In (2) we multiply out in the left-hand sum and write the index range somewhat more conveniently in the middle sum. We exchange the sums in the right-hand double-sum.

• In (3) we shift the index of the inner sum to start from $i=0$.

• In (4) we apply the finite geometric summation formula.

• In (5) we do some simplifications.

• In (6) we multiply out and do some simplifications.

• In (7) we apply the finite geometric summation formula again.

• In (8) and (9) we do some more simplifications.

• Looks like I'm really gonna need to do some review on the geometric summation formula, but otherwise this was pretty helpful. Thanks! – lordgankoo Sep 4 '17 at 20:24
• @lordgankoo: You're welcome! :-) I've adjusted the expression in (7) somewhat to better see the connection with the formula in (4). Regards, – Markus Scheuer Sep 4 '17 at 20:30

Just use a sum of the geometric series.

It's $$\sum_{i=1}^n\frac{3^k(3^{n-k+1}-1)}{3-1}=\frac{n3^{n+1}}{2}-\frac{1}{2}\frac{3(3^n-1)}{2}=\frac{2n3^{n+1}-3^{n+1}+3}{4}.$$

• I'm having some trouble understanding how you got even that first step. Where does the $3^i$ come from? How did the lower bound become $i=1$ again? – lordgankoo Sep 4 '17 at 18:29
• @lordgankoo $a_1=3^k$ in our progression. I fixed. It was typo. – Michael Rozenberg Sep 4 '17 at 18:31

Because the other answer already discusses about computing $\sum_{k=1}^n \sum_{i=k}^n 3^i$, here's another way to compute $\sum_{i=1}^n i3^i$

\begin{eqnarray} S & = & \sum_{i=1}^n i 3^i \\ & = & 1.3^1 + 2.3^2 + 3.3^3 + \cdots + n.3^n \\ 3S & = & \space\space\space\space\space\space\space\space\space\space\space\space 1.3^2 + 2.3^3 + \cdots + (n-1).3^n + n.3^{n+1} \\ \end{eqnarray}

Therefore, on subtracting, we get $$S - 3S = (3^1 + 3^2 + 3^3 + \cdots + 3^n) - n.3^{n+1}$$ $$\implies -2S = 3\left(\frac{3^n-1}{2}\right) - n.3^{n+1} = \frac{(1-2n)3^{n+1}-3}{2}$$ $$\implies S = \frac{(2n-1)3^{n+1}+3}{4}$$

The inner sum is a geometric series. It can be expanded as follows:

$$\sum_{k=1}^n\sum_{i=k}^n3^i=\sum_{k=1}^n(\sum_{i=k}^n3^i)=\sum_{k=1}^n\frac{3^k-3^{n+1}}{1-3}=\sum_{k=1}^n\frac{3^{n+1}-3^k}{2}=\frac{n3^{n+1}}2-\frac12\sum_{k=1}^n3^k$$

The rest should be pretty straight-forward.