# Nested Summation Formula Help

I'm currently taking a discrete mathematics course, and we're learning about summation formulas. I need to create a formula for the nested summation

$$\sum_{i=0}^{n} \sum_{j=0}^i 2^i$$

I started with the inner summation:

$$\sum_{j=0}^{i} 2^i$$

and arrived at

$$2^{i+1} - 1$$

I plugged this into the outer summation

$$\sum_{i=0}^{n} 2^{i+1}-1$$

The following is my work for evaluating the outer sum:

$$\sum_{i=0}^{n} 2^{i+1}- \sum_{i=0}^{n}1 = 2(\sum_{i=0}^{n} 2^{i})- n = 2(2^{n+1} - 1) - n = 2^{n+2} - 2 - n$$

So my final answer is $\ 2^{n+2}-2-n$. However, when I checked my answer on Wolfram Alpha, it says my answer should be $\ 2^{n+1}(n+1)$ check here Wolfram source. Can someone please explain how I am supposed to arrive at what Wolfram Alpha is saying and point out where I went wrong with my computation? Thank you!

• Hint: your inner summation is not correct. Observe that the summand $2^i$ is independend of $j$. So the inner sum is $\sum_{j=0}^i 2^i = 2^i\sum_{j=0}^i1 = 2^i(i + 1)$. – jflipp Oct 8 '17 at 21:59
• @jflipp but since its executing from j to i doesn't that mean it will sum 2^i j times? – danielschnoll Oct 8 '17 at 22:06
• The answer from Wolframalpha is $2^{n+1} n+1=n2^{n+1}+1$, which is not the same as $2^{n+1}(n+1)=n2^{n+1}+2^{n+1}$. – Hypergeometricx Oct 8 '17 at 22:30

A much neater method!

\begin{align} S&=\sum_{i=0}^n\sum_{j=0}^i 2^i\\ &=\sum_{i=0}^n (i+1)2^i\\ &=\sum_{i=0}^n \overbrace{2i2^i-i2^i}^{i2^i}+2^i\\ &=\sum_{i=0}^n i2^{i+1}-(i-1)2^i\\ &=n2^{n+1}-(-1)2^0&&\text{(by telescoping)}\\ &=\color{red}{n2^{n+1}+1}\end{align}

(Original answer below) \scriptsize\begin{align} \sum_{i=0}^{n} \sum_{j=0}^i 2^i &=\sum_{j=0}^n\sum_{i=j}^n 2^i &&(0\le j\le i\le n)\\ &=\sum_{j=0}^n 2^j\cdot \frac {2^{n-j+1}-1}{2-1}\\ &=\sum_{j=0}^n 2^{n+1}-2^j\\ &=(n+1)2^{n+1}-\frac {2^{n+1}-1}{2-1}\\ &=(n+1)2^{n+1}-2^{n+1}+1\\ &=\color{red}{n2^{n+1}+1}\end{align} Alternatively, \scriptsize\begin{align} S&=\sum_{i=0}^n\sum_{j=0}^i 2^i\\ &=\sum_{i=0}^n 2^i\sum_{j=0}^i 1\\ &=\sum_{i=0}^n (i+1)2^i\\ &=1(2^0)+2(2^1)+3(2^2)+4(2^3)+\cdots+(n+1)2^n\\\\ \times 2:\qquad 2S &=\quad\qquad 1(2^1)+2(2^2)+3(2^3)+\cdots+\quad \quad n2^n+(n+1)2^{n+1}\\\\ \text{Subtracting:}\quad 2S-S&=\;-2^0\;\;\;-2^1\quad\ -2^2\quad -2^3\ -\cdots\qquad\ \ -2^n+(n+1)2^{n+1} \\\\ S&=-(1+2+2^2+2^3+\cdots+2^n)+(n+1)2^{n+1}\\\\ &=-\frac{2^{n+1}-1}{2-1}+(n+1)2^{n+1}\\ &=\color{red}{n2^{n+1}+1}\end{align}

• Thanks for the detailed response! – danielschnoll Oct 9 '17 at 2:25
• You're welcome! Glad you like it :) – Hypergeometricx Oct 9 '17 at 11:04
• See addendum for a much shorter method! – Hypergeometricx Oct 9 '17 at 12:38

You did the following sum \begin{eqnarray*} \sum_{j=0}^{i} 2^{\color{red}{j}} \end{eqnarray*} You should have done \begin{eqnarray*} \sum_{j=0}^{i} 2^{\color{red}{i}} =(i+1)2^i \end{eqnarray*} The second sum then gives \begin{eqnarray*} \sum_{i=0}^{n} (i+1)2^i = n2^{n+1} +1. \end{eqnarray*}