5
$\begingroup$

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?

$\endgroup$
11
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

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

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.

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

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

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