3

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.

Felix Marin
  • 89,464
b_pcakes
  • 1,501

3 Answers3

1

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

b_pcakes
  • 1,501
polfosol
  • 9,245
  • 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 07:38
  • Nevermind! I've figured it out after looking on wikipedia: https://en.wikipedia.org/wiki/Binomial_coefficient#Series_involving_binomial_coefficients – b_pcakes Oct 24 '16 at 07:44
  • 1
    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 08: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 08:17
1

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

robjohn
  • 345,667
0

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

Hypergeometricx
  • 22,657