Sum of sum of binomial coefficients $\sum_{j=1}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}$ I know there is no simple way to solve the sum:
$$\sum_{k=0}^{j}{{n}\choose{k}}$$
But what about the equation:
$$\sum_{j=1}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}$$
Are there any simplifications or good approximations for this equation?
 A: Let's see.
$\begin{array}\\
s(n)
&=\sum_{j=1}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}\\
&=-1+\sum_{j=0}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}\\
&=-1+\sum_{k=0}^{n}\sum_{j=k}^{n}{{n}\choose{k}}\\
&=-1+\sum_{k=0}^{n}(n-k+1){{n}\choose{k}}\\
&=-1+\sum_{k=0}^{n}(n+1){{n}\choose{k}}-\sum_{k=0}^{n}k{{n}\choose{k}}\\
&=-1+(n+1)2^n-\sum_{k=0}^{n}k\dfrac{n!}{k!(n-k)!}\\
&=-1+(n+1)2^n-\sum_{k=1}^{n}\dfrac{n!}{(k-1)!(n-k)!}\\
&=-1+(n+1)2^n-n\sum_{k=1}^{n}\dfrac{(n-1)!}{(k-1)!(n-k)!}\\
&=-1+(n+1)2^n-n\sum_{k=1}^{n}\binom{n-1}{k-1}\\
&=-1+(n+1)2^n-n\sum_{k=0}^{n-1}\binom{n-1}{k}\\
&=-1+(n+1)2^n-n2^{n-1}\\
&=-1+2^{n-1}(2(n+1)-n)\\
&=-1+2^{n-1}(n+2)\\
\end{array}
$
A pleasant surprise.
A: There are. Start rewriting the double sum as
$$\begin{align}
\sum_{j=1}^n \sum_{k=0}^j \binom{n}{k}
&= \sum_{j=1}^n \sum_{k=0}^n \binom{n}{k} \mathbb{1}_{k\leq j}
= \sum_{k=0}^n \sum_{j=1}^n \binom{n}{k} \mathbb{1}_{k\leq j}
= \sum_{k=0}^n \sum_{j=k}^n \binom{n}{k} - 1
= \sum_{k=0}^n \binom{n}{k} \sum_{j=k}^n 1 = 1 \\
&= \sum_{k=0}^n \binom{n}{k} (n-k+1) -1
= (n+1)\sum_{k=0}^n \binom{n}{k} -  \sum_{k=0}^n k \binom{n}{k} -1
\end{align}$$
Now, this becomes easy to compute -- both sums have closed forms.
A: $$\begin{align}
\sum_{j=\color{red}0}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}
&=\sum_{k=0}^n\sum_{j=k}^n\binom nk\\
&=\sum_{k=0}^n (n-k+1)\binom n{n-k}\\
&=\sum_{k=0}^n (j+1)\binom nj
&&\text{putting }j=n-k\\
&=\sum_{k=0}^n j\binom nj+\sum_{k=0}^n \binom nj\\
&=n 2^{n-1}+2^n\\
\sum_{j=\color{red}1}^n\sum_{k=0}^n\binom nk&=\sum_{j=\color{red}0}^n\sum_{k=0}^n\binom nk-1\\
&=n 2^{n-1}+2^n-1\\
&=(n+2)2^{n-1}-1\quad\blacksquare
\end{align}$$
A: Basically it’s just a matter of reversing the order of summation, much as you might reverse the order of integration of a double integral, though the lower limit of $1$ on the outer summation requires a little adjustment.
$$\begin{align*}
\sum_{j=1}^n\sum_{k=0}^j\binom{n}k&=\sum_{j=0}^n\sum_{k=0}^j\binom{n}k-\binom{n}0\\
&=\sum_{k=0}^n\sum_{j=k}^n\binom{n}k-1\\
&=\sum_{k=0}^n(n-k+1)\binom{n}k-1\\
&=(n+1)\sum_{k=0}^n\binom{n}k-\sum_{k=0}^nk\binom{n}k-1\\
&=(n+1)2^n-\sum_{k=0}^nn\binom{n-1}{k-1}-1\\
&=(n+1)2^n-1-n\sum_{k=0}^{n-1}\binom{n-1}k\\
&=(n+1)2^n-1-n2^{n-1}\\
&=(n+2)2^{n-1}-1
\end{align*}$$
