How to prove that $\sum_{i=0}^n 2^i\binom{2n-i}{n} = 4^n$. So I've been struggling with this sum for some time and I just can't figure it out. I tried proving by induction that if the sum above is a $S_n$ then $S_{n+1} = 4S_n$, but I didn't really succeed so here I am. Thanks in advance.

I can give a mildly ugly proof by induction. Let
$$S_n=\sum_{k=0}^n2^k\binom{2n-k}n=\sum_{k=0}^n2^k\binom{2n-k}{n-k}=\sum_{k=0}^n2^{n-k}\binom{n+k}n\;,$$
and assume that $S_n=4^n=2^{2n}$. Then
$$\begin{align*}
S_{n+1}&=\sum_{k=0}^{n+1}2^{n+1-k}\binom{n+1+k}{n+1}\\
&=\sum_{k=0}^{n+1}2^{n+1-k}\left(\binom{n+k}n+\binom{n+k}{n+1}\right)\\
&=\sum_{k=0}^{n+1}2^{n+1-k}\binom{n+k}n+\sum_{k=0}^{n+1}2^{n+1-k}\binom{n+k}{n+1}\\
&=\binom{2n+1}n+2\sum_{k=0}^n2^{n-k}\binom{n+k}n+\sum_{k=0}^{n+1}2^{n+1-k}\binom{n+k}{n+1}\\
&=\binom{2n+1}n+2^{2n+1}+\sum_{k=1}^{n+1}2^{n+1-k}\binom{n+k}{n+1}\\
&=2^{2n+1}+\binom{2n+1}n+\binom{2n+1}{n+1}+\sum_{k=1}^n2^{n+1-k}\binom{n+k}{n+1}\\
&=2^{2n+1}+\binom{2n+2}{n+1}+\sum_{k=0}^{n-1}2^{n-k}\binom{n+1+k}{n+1}\\
&=2^{2n+1}+\binom{2n+2}{n+1}+\frac12\left(S_{n+1}-\binom{2n+2}{n+1}-2\binom{2n+1}{n+1}\right)\\
&=2^{2n+1}+\binom{2n+2}{n+1}+\frac12\left(S_{n+1}-2\binom{2n+2}{n+1}\right)\\
&=2^{2n+1}+\frac12S_{n+1}\;,
\end{align*}$$
so $\frac12S_{n+1}=2^{2n+1}$, and $S_{n+1}=2^{2n+2}=4^{n+1}$.
