Sunday, October 28, 2018

algebra precalculus - 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?


Answer



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.



No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...