2
$\begingroup$

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!

$\endgroup$
  • $\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 '17 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$ – danielschnoll Oct 8 '17 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$ – hypergeometric Oct 8 '17 at 22:30
1
$\begingroup$

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


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

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

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