Exercise C.4.6

\star Professor Rosencrantz flips a fair coin nn times, and so does Professor Guildenstern. Show that the probability that they get the same number of heads is (2nn)/4n\binom{2n}{n}/4^n. (Hint: For Professor Rosencrantz, call a head a success; for Professor Guildenstern, call a tail a success.) Use your argument to verify the identity

k=0n(nk)2=(2nn) \sum_{k=0}^n\binom{n}{k}^2 = \binom{2n}{n}

Let's do what the hint says: call tails for Professor Guildenstern a success and heads - failure. They have the same numbers of heads when they have k+(nk)=nk + (n - k) = n successes out of 2n2n trials.

Pr{R=G}=b(n;2n;1/2)=(2nn)12n12n=(2n)/4n \Pr\{R=G\} = b(n;2n;1/2) = \binom{2n}{n} \frac{1}{2^n} \frac{1}{2^n} = \binom{2}{n}/4^n

Alternatively, we can just calculate the probability and see what happens:

Pr{R=G}=k=0nPr{R=k}Pr{G=nk}=k=0n(nk)12n(nnk)12n=14nk=0n(nk)(nnk)=14nk=0n(nk)2 \begin{aligned} \Pr\{R=G\} &= \sum_{k=0}^n \Pr\{R=k\}\Pr\{G=n-k\} \\ &= \sum_{k=0}^n \binom{n}{k} \cdot \frac{1}{2^n} \cdot \binom{n}{n-k} \cdot \frac{1}{2^n} \\ &= \frac{1}{4^n} \sum_{k=0}^n \binom{n}{k} \binom{n}{n-k} \\ &= \frac{1}{4^n} \sum_{k=0}^n \binom{n}{k}^2 \end{aligned}

Those are two ways we can express the same value. This let's us verify the identity.