# How to prove combinatorial identity $2^{2n}=\sum_{k=0}^{n} 2^k \times \binom{2n-k}{n}$ [duplicate]

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.

• Hint: with $k\mapsto n-k$ the conjecture is equivalent to $n!=\left.\sum_{k=0}^n\frac{(n+k)!}{k!}x^{n+k}\right|_{x=\frac12}$. – J.G. Oct 14 '19 at 5:45
• – Martin Sleziak Oct 30 '19 at 5:32

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.