I would appreciate if somebody could help me with the following problem:

Prove the identity $$2^{2n}=\sum_{k=0}^{n} 2^k \times \binom{2n-k}{n}$$ (for $n$ a nonnegative integer) combinatorially.

I've tried transforming it into $$\sum_{k=0}^{n} \frac{1}{2^{2n-k}} \times \binom{2n-k}{n}=1$$ and looking for a probabilistic proof.


Here is a way to rephrase Zac's proof as a combinatorial argument.

Question: How many binary sequences of length $2n+1$ have more ones than zeroes?

Answer $1$: Half of the sequences have more ones than zeroes, since a sequence has more ones than zeroes if and only if its complement does not. There are $2^{2n+1}$ sequences total; half of this is $2^{2n}$.

Answer $2$: Such a sequence will have at least $n+1$ ones. Let us count how many such sequences there are such that the $(n+1)^{st}$ instance of one (reading from left to right) occurs at spot number $2n+1-k$. Among the first $2n-k$ symbols, there will be exactly $n$ ones, whose locations can be chosen in $\binom{2n-k}n$ ways. Symbol number $2n-k+1$ must be a one, and then the remaining $k$ symbols can be chosen arbitrarily in $2^k$ ways. Summing over $k$, the number of possible sequences is $\sum_{k=0}^n \binom{2n-k}{n}2^k$.

Note the bounds on $k$; $k=0$ corresponds to the situation where the $(n+1)^{st}$ one occurs at spot $2n+1$, and $k=n$ corresponds to the case where the $(n+1)^{st}$ one occurs at spot $n+1$. These are indeed the furthest possible locations.


A probabilistic argument is possible.

Hint: Consider two players, $A$ and $B$, who play a sequence of rounds in a game against each other in which both players are equally likely to win each round. Suppose that the first player to win $n+1$ rounds wins the game. Consider the probability that player $A$ wins the game.


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