# Binomial identity and probability

The identity
$\displaystyle \sum k \binom{n}{k} = n 2^{n-1}$
is pretty standard, and one can prove it algebraically by cancelling the k in the sum with the binomial coefficient and then using the binomial theorem summation or a combinatorial proof that goes like this.
Choose a k element committee with from n members with one of the comittee member being made the chairperson.

A third proof using probability goes like this. First divide throughout by $2^n$. Next consider tossing n fair coins with probability $p=\frac{1}{2}$ of turning up heads or tails. The expected number of heads is $\frac{n}{2}$. On the other hand, the probability of having exactly k heads (and hence n-k tails) is $\binom{n}{k} (p)^k (1-p)^{n-k}$.
Thus the expected value is
$\displaystyle \sum k \binom{n}{k} (\frac{1}{2})^{n}= \frac{n}{2}.$

From a probabilistic point of view, it could very well be the fact that one proves the expected value of is np by using the identity so this third proof isn’t really a proof but a nice application.

This entry was posted in Combinatorics, Probability. Bookmark the permalink.