Nested Summation Formula Help

Question

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!

Answer 1

Addendum

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

---

Answer 2

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