Proof for a binomial equation

Question

I'm trying to formally write out the problem: Light bulb color problem when I come up with the following equation

$$\sum_{i=0}^{k-1}{C}_{2k-1}^{2k-1-i}{p}^{2k-1-i}{(1-p)}^{i}=\sum_{i=0}^{k-1}{C}_{2k}^{2k-i}{p}^{2k-i}{(1-p)}^{i}+\frac{1}{2}{C}_{2k}^{k}{p}^{k}{(1-p)}^{k}$$

where it is supposed to hold for all $k\geq1$. Let's forget the original light bulb problem for a while. If we just want to prove the above equation, how shall we do it? I tried induction and it seemed difficult and baffling... Is there any idea or perhaps tricks one can use to establish it? What is the general approach for establishing these kind of complex combinatorial equations? (By the way, I know from the light bulb problem that it must be true for $0\leq p\leq1$, but does it also hold for any $p$ beyond that domain?)

---

Edit: I vaguely remember there's a theorem or something that says if the above equation holds for any $0\leq p\leq1$ then it must hold for any $p\in\mathbb{R}$. Does any one know what that theorem is?

Answer 1

About the combinatorial question: the proof follows from the identity $$ {2k-1 \choose i-1} + {2k-1 \choose i} = {2k \choose i} $$ Thus $$ \sum_{i=0}^{k-1} {2k\choose i} p^{2k-i} (1-p)^i = \sum_{i=0}^{k-1} {2k-1 \choose i} p^{2k-i} (1-p)^i + \sum_{i=0}^{k-1} {2k-1 \choose i-1} p^{2k-i} (1-p)^i $$ which implies $$ \sum_{i=0}^{k-1} {2k\choose i} p^{2k-i} (1-p)^i = \sum_{i=0}^{k-2} {2k-1 \choose i} p^{2k-1-i} (1-p)^i + {2k-1 \choose k-1} p^{k+1} (1-p)^{k-1} $$ and $$ \frac{1}{2}{2k\choose k} = {2k-1\choose k-1} $$ implying that $$ {2k-1 \choose k-1} p^{k+1} (1-p)^{k-1} + \frac{1}{2}{2k\choose k} p^{k} (1-p)^{k} = {2k-1\choose k-1 } p^{k} (1-p)^{k-1} $$ which establishes your identity.

About your "Edit" question, I think you mean the theorem in complex calculus that states that, if an analytic function is constant over an interval, it is constant everywhere.

Answer 2

A coin has a chance $p$ of landing heads. Among an odd number ($2k-1$) of tosses, what are the chances there are more heads than tails?

Let's look at two solutions.

1. The number of heads is $k$, $k+1$, $k+2$, $...$, or $2k-1$. Sum the chances of each of these events.

2. Toss the coin one more time!

   If the number of heads is now $k+1$, $k+2$, $...$, or $2k$, then originally there were at least $k$ heads. Sum these chances.

   If the number of heads is now exactly $k$, it's uncertain whether there were $k-1$ or $k$ heads among the original $2k-1$ tosses. It all depends on whether the last toss was a head: there were $k$ heads originally if and only if the last toss was a tail. Do the following: randomly write down all $2k$ results--of which $k$ are heads and $k$ are tails, by assumption. One of them represents the last toss, but which? We don't know, but we do know it has equal chances of being in any of the $2k$ positions. Since $k$ of those are tails, there is a $k/(2k)=1/2$ chance the last toss was a tail.

In solution (1), the chance of exactly $i$ tails, equivalent to $2k-1-i$ heads, is given by the Binomial Distribution for $2k-1$ tosses,

$${\Pr}_{2k-1}(2k-1-i) = \binom{2k-1}{i}p^{2k-1-i}(1-p)^i = C_{2k-1}^{2k-1-i}p^{2k-1-i}(1-p)^i.$$

The sum goes from $i=0$ to $i=k-1$. That's the left hand side of the equation in the question.

In solution (2), the chance of exactly $i$ tails is equivalent to $2k-i$ heads, given by

$${\Pr}_{2k}(2k-i) = \binom{2k}{i}p^{2k-i}(1-p)^i = C_{2k}^{2k-i}p^{2k-i}(1-p)^i.$$

Totaling these for $i=0, 1, \ldots, k-1$ gives the summation to the right of the equation in the question. The chance that the last toss is a tail and all $2k$ tosses are heads is the product

$${\Pr}_{2k}\left(\text{last toss is tail}\,|\,k\text{ heads}\right){\Pr}_{2k}\left(k\text{ heads}\right) = \frac{1}{2}\binom{2k}{k}p^{2k-k}(1-p)^k = \frac{1}{2}C_{2k}^kp^k(1-p)^k.$$

This is the extra term at the right of the equation. Solution (2) therefore produces the formula on the right hand side.

Thus, the equation holds for all $k$ because it gives two ways of expressing the chance of observing a majority of heads in any odd number of tosses.

---

The general approach exemplified here is to count the same thing in two different ways. It's a powerful method, advocated particularly by combinatorialists (people who specialize in counting things). Many complicated formulas turn out to have simple, illuminating proofs of this nature. For details, see Richard Stanley's Enumerative Combinatorics. (Volume 1 is available on the Web--Google it.)

---

Let's address the last part of the question. Both sides of the equation are obviously polynomials in $p$. Their difference is a polynomial of degree at most $2k$. It is zero for all valid probabilities $p$. There are more than $2k+1$ probabilities (there are infinitely many of them in the interval from $0$ to $1$). Since a polynomial of degree $n$ is completely determined by its values at any $n+1$ numbers, the difference is the zero function--and in particular equals zero for any number $p$.