Identity involving sums of binomial coefficients

Question

I'm trying to prove the following: $$\sum_{k=0}^n 2^k\binom{2n-k}{n}=4^n$$

I've thought about induction, but there's not a very nice way to change the LHS from the $n$ case to the $n+1$ case by multiplying by $4$, at least, none that I can see.

I've also thought about trying to put a combinatorial argument together, by somehow arguing that the LHS counts $n$-letter words made from a $4$-letter alphabet, but I can't get the set being counted to partition in a way that sensibly represents the different terms of the sum.

I believe the identity is true, not only because I've tried a few small values of $n$, but also because Wolfram Alpha simplifies it for me. It just won't tell me how.

Thanks in advance for any insights.

---

Additional context: This identity arose while studying answers to this probability question: Expected number of draws to find a match

Answer 1

There is a nice combinatorial proof involving walks in the 2D plane.

Consider $4^n$ as the set of strings of $2n$ symbols, each of which is either $U$ or $R$, for "up" and "right". This determines a walk in a 2D lattice, starting at $(0,0)$ and ending at some point $(m,2n-m)$ for some $0\le m \le 2n$.

Let $S$ be the following set of points: $$ S=\{(n,n-k):0\le k\le n\}\cup\{(n-k,n):0\le k\le n\} $$ That is, $S$ consists of the lattice points on the top and right boundary of the square $[0,n]\times[0,n]$.

Every walk must eventually hit $S$. Consider the last point in $S$ that the walk visits. Whenever $k>1$, I claim that the number of walks for which the last point in $S$ they hit is $(n,n-k)$ is equal to $$ \binom{2n-k}{n}2^{k-1} $$ Namely, such a walk is determine by a path from $(0,0)$ to $(n,n-k)$, the number of which is $\binom{n+n-k}{n}$, followed by a "right" step, followed by ${k-1}$ arbitrary steps.

Combining this with the cases where the last visited point is on the top boundary of the square, $(n-k,n)$, and the case where the last visited point is $(n,n)$, your summation is attained.