2
$\begingroup$

I solved this problem with the help of someone else who showed me a property that made this solution simple, but I now have to use a similar technique in a different problem and for the life of me I cannot remember what that property was. It is some property of sums of binomial coefficients, something that I am not very well-versed in.

The original problem was this: Prove that when $N=2(d+1)$, the following is true: $$0.5 = (1/2^N) * \sum_{k=0}^d {N-1 \choose k}$$

The person who helped me showed me a property that involved using symmetry properties to change the summation into multiple sums that one can easily simplify (he showed that the sum equalled two times a sum that is one-half of the above sum or something like that), but I cannot remember what that property was for the life of me.

My new problem is likely solvable using the same technique, and I could solve it if I just knew what that technique was:

Find $d$ such that: $$0.5 = (1/2^{20}) * \sum_{k=0}^d {20 \choose k}$$

I don't need the direct answer to the problem; if I can just get the property that makes this problem solvable I can happily do the rest.

$\endgroup$
  • 1
    $\begingroup$ Well in this case no such $d$ exists, so you're out of luck. Try to see why $d=9$ gives a RHS that is too small, and $d=10$ give a RHS that is too large by exactly the same amount. $\endgroup$ – Marc van Leeuwen Sep 17 '13 at 16:51
  • $\begingroup$ Your first formula is wrong. It becomes right after you either replace $2^N$ by $2^{N-1}$ or $0.5$ by $0.25$ (but not both of course). $\endgroup$ – Marc van Leeuwen Sep 21 '13 at 9:51
2
$\begingroup$

One way of looking at the problem is to make a probabilistic interpretation. The expression $$\sum_{k=0}^d \binom{20}{k}\left(\frac{1}{2}\right)^{20}$$ is the probability of getting $\le d$ heads in $20$ tosses of a fair coin.

Use symmetry to argue that there is no $d$ such that the probability of $\le d$ heads is exactly $0.5$.

More "algebraically," use the fact that $\binom{20}{k}=\binom{20}{20-k}$ to argue that $$\sum_{0}^9 \binom{20}{k}=\sum_{11}^{20}\binom{20}{k}.$$ This should be enough to show that there is no $d$ with the required property.

More informally, the binomial coefficients $\binom{20}{k}$ are symmetric about $k=10$.

The same symmetry argument shows that if $n=2m+1$ is odd. then $\frac{1}{2^n}\sum_{d=0}^m \binom{n}{k}=0.5$.

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