# Proof involving $\sum_{k=0}^d {N \choose k}$; missing property to make this work

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.

• 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. – Marc van Leeuwen Sep 17 '13 at 16:51
• 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). – Marc van Leeuwen Sep 21 '13 at 9:51

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