Here's my proof: Let q=1-p, so that for all i+j=n, the coefficient of p^i q^j in the binomial expansion of (p+q)^n gives the probability of getting heads i times and tails j times. Meanwhile, the coefficient of p^i q^j in the binomial expansion of (-p+q)^n is (-1)^i times the aforementioned probability. So if we add the two expressions and divide by 2, we obtain just those terms in which i is even. That is, the probability of an even number of heads in n tosses is exactly ((p+q)^n + (-p+q)^n)/2, and since (p+q)^n = 1, that probability is bigger than 1/2. Can anyone find a "bijective" proof of this formula for the probability of an even number of heads? Or, alternatively, an "injective" or "surjective" proof that the probability is greater than or equal to 1/2? (I'm not completely sure what I mean by this, but I think I'll recognize it when I see it.) Jim On Monday, March 21, 2016, James Propp <jamespropp@gmail.com> wrote:
Show that, for any bias p < 1/2, and any positive integer n, if you take a biased coin that shows heads with probability p and toss it n times, the number of times the coin shows heads is likelier to be even than odd.
I know one proof (by way of an exact formula for the probability in question) but I'll bet some of you will find other ways to prove this.
Jim Propp