7
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – lordgankoo Sep 4 '17 at 18:29
  • $\begingroup$ @lordgankoo $a_1=3^k$ in our progression. I fixed. It was typo. $\endgroup$ – Michael Rozenberg Sep 4 '17 at 18:31
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.