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.
 A: 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}$$
A: 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
A: $$\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}$$
