2
$\begingroup$

How to prove the following combinatorical identity using a combinatorical proof?

$$\sum_{k=0}^n{{2n+1}\choose k}=2^{2n}$$

I solved it with an algebric proof with Newton's binomial and the symmetry of the binom.

$\endgroup$
10
$\begingroup$

The left hand side counts the ways to pick at most $n$ out of $2n+1$ objects. Twice the right hand side counts all subsets of a set of $2n+1$ objects. To get from an arbitrary subset to a subset of size $\le n$, just either take the subset itself or its complement (depending on the size of the givne subset).

$\endgroup$
9
$\begingroup$

We give a probabilistic proof, so not an answer to the question. We want to show that $$\sum_{k=0}^n \binom{2n+1}{k}\frac{1}{2^{2n+1}}=\frac{1}{2}.\tag{1}$$

Alicia throws $2n+1$ fair coins onto a coffee table. She will be happy if she sees $\le n$ heads. The probability she will be happy is the left-hand side of (1).

The coffee table is made of glass, and Beti is under the table (don't ask!). Beti will be happy if she sees $\le n$ tails.

It is clear that Beti will be happy if and only if Alicia is not. But by symmetry their probabilities of being happy are the same, so each is equal to $\dfrac{1}{2}$.

$\endgroup$
  • $\begingroup$ +1 for happyness. I bet Beti is just a smart dog looking at coin under a table $\endgroup$ – Jean-Sébastien Sep 11 '13 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.