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!

  • $\begingroup$ 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)$. $\endgroup$
    – jflipp
    Oct 8, 2017 at 21:59
  • $\begingroup$ @jflipp but since its executing from j to i doesn't that mean it will sum 2^i j times? $\endgroup$ Oct 8, 2017 at 22:06
  • $\begingroup$ 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}$. $\endgroup$ Oct 8, 2017 at 22:30

2 Answers 2



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

  • $\begingroup$ Thanks for the detailed response! $\endgroup$ Oct 9, 2017 at 2:25
  • $\begingroup$ You're welcome! Glad you like it :) $\endgroup$ Oct 9, 2017 at 11:04
  • $\begingroup$ See addendum for a much shorter method! $\endgroup$ Oct 9, 2017 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*}


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.