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

$$\sum_{j=1}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}$$

Are there any simplifications or good approximations for this equation?

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

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.

• You are right. I'll fix it. Thanks. Upvoted. – marty cohen Apr 30 '16 at 23:31
• Reciprocated. $\,$ – Brian M. Scott Apr 30 '16 at 23:33

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.

• Nice when two independent answers agree. – marty cohen Apr 30 '16 at 23:30
• I made the same error. Great minds, eh? – marty cohen Apr 30 '16 at 23:33
• Great minds err alike? :) I had forgotten a -1 (since $j=0$ cannot happen in the original sum). – Clement C. Apr 30 '16 at 23:34

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