Combinatorical proof $\sum\limits_{k=0}^n{{2n+1}\choose k}=2^{2n}$

Question

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.

Answer 1

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).

Answer 2

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}$.