# How to simplify summation with binomial coefficients

Is it possible to simplify this sum further without calculating it ?:

$$\sum_{t = 0}^{4}\left[1 - \sum_{a = 0}^{t}{4 \choose a}\left(1 \over 2\right)^{4}\right]$$

Normally I would use the binomial theorem on something similar to the inside sum but that doesn't work here. I know that $4$ is a small value but I was wondering in general.

• It is correct and has been solved – b_pcakes Oct 24 '16 at 8:19

Hint: You only need to show that $$\sum_{i=0}^n{\sum_{j=0}^i\binom{n}{j}}=2^{n-1}n + 2^n$$ Then your summation is simplified as: \begin{align} \sum_{i=0}^n\left(1-\sum_{j=0}^i\binom{n}{j}\left(\frac{1}{2}\right)^n\right)&=n + 1-\sum_{i=0}^n\sum_{j=0}^i\binom{n}{j}\left(\frac{1}{2}\right)^n\\&=n+1-2^{-n}\sum_{i=0}^n{\sum_{j=0}^i\binom{n}{j}}=\frac{n}{2} \end{align}

• Could you provide a little more detail on proving the first part, since that is really the meat of the question. I've simplified it to $\sum_{i = 1}^{n+1}i{n \choose {n+1-i}}$ but that doesn't seem to make it better. – b_pcakes Oct 24 '16 at 7:38
• Nevermind! I've figured it out after looking on wikipedia: en.wikipedia.org/wiki/… – b_pcakes Oct 24 '16 at 7:44
• So I figured it out, the answer is slightly different (it is $n2^{n-1} + 2^n$), but the answer in the end is still $n/2$ because $\sum_0^n 1 = n+1$, not $n$. – b_pcakes Oct 24 '16 at 8:01
• @b_pcakes You are right. My formula standed for the case were summation limit is $i=n-1$ and not $n$ – polfosol Oct 24 '16 at 8:17

Let's generalize this to \begin{align} \sum_{k=0}^n\left(1-\frac1{2^n}\sum_{j=0}^k\binom{n}{j}\right) &=(n+1)-\frac1{2^n}\sum_{j=0}^n\sum_{k=j}^n\binom{n}{j}\tag{1}\\ &=(n+1)-\frac1{2^n}\sum_{j=0}^n(n-j+\color{#C00000}{1})\binom{n}{j}\tag{2}\\ &=(n+1)-\frac1{2^n}\left(\color{#C00000}{2^n}+\sum_{j=0}^nj\binom{n}{j}\right)\tag{3}\\ &=(n+1)-\frac1{2^n}\left(2^n+\sum_{j=0}^nn\binom{n-1}{j-1}\right)\tag{4}\\ &=(n+1)-\frac1{2^n}\left(2^n+n2^{n-1}\right)\tag{5}\\[9pt] &=\frac n2\tag{6} \end{align} Explanation:
$(1)$: sum the $1$ and switch the order of summation
$(2)$: evaluate the inner sum
$(3)$: $\sum\limits_{j=0}^n\binom{n}{j}=2^n$ and substitute $j\mapsto n-j$ in the sum
$(4)$: $\binom{n}{j}=\frac nj\binom{n-1}{j-1}$
$(5)$: $\sum\limits_{j=0}^n\binom{n-1}{j-1}=2^{n-1}$
$(6)$: evaluate

\begin{align} \sum_{t=0}^4\sum_{a=t}^4\binom 4a &=\sum_{a=0}^4\sum_{t=a}^4 \binom 4a\\ &=\sum_{a=0}^4\binom 4a\sum_{t=a}^4 1\\ &=\sum_{a=0}^4 \binom 4a (5-a)\\ &=5\cdot 2^4-4\sum_{a=0}^3 \binom 3a\\ &=5\cdot 2^4-4\cdot 2^3\\ \sum_{t = 0}^4\left( 1 - \sum_{a=0}^t {4 \choose a}\left(\frac{1}{2}\right)^4\right) &=\sum_{t=0}^4 1-\frac 1{2^4}\sum_{t=0}^4\sum_{a=0}^t \binom 4a \\ &=5-\frac 1{2^4}\cdot (5\cdot 2^4-4\cdot 2^3)\\ &=2 \end{align}