3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It is correct and has been solved $\endgroup$ – b_pcakes Oct 24 '16 at 8:19
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – b_pcakes Oct 24 '16 at 7:38
  • $\begingroup$ Nevermind! I've figured it out after looking on wikipedia: en.wikipedia.org/wiki/… $\endgroup$ – b_pcakes Oct 24 '16 at 7:44
  • 1
    $\begingroup$ 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$. $\endgroup$ – b_pcakes Oct 24 '16 at 8:01
  • $\begingroup$ @b_pcakes You are right. My formula standed for the case were summation limit is $i=n-1$ and not $n$ $\endgroup$ – polfosol Oct 24 '16 at 8:17
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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