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