combinatorics - How to prove combinatorial identity $2^{2n}=sum_{k=0}^{n} 2^k times binom{2n-k}{n}$

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.

Answer

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.