Calculate the sum: $C_{2n}^n+2C_{2n-1}^n+4C_{2n-2}^n+...+2^nC_n^n$ Calculate this sum:$$C_{2n}^n+2C_{2n-1}^n+4C_{2n-2}^n+...+2^nC_n^n.$$
What I tried:
$$ C^n_{2n}=\frac{(2n)!}{(n!)^2}$$
$$ 2C^n_{2n-1}=\frac{2(2n-1)!}{n!(n-1)!}=\frac{2n(2n)!}{n!n!(2n)}=\frac{(2n)!}{(n!)^2}$$
$$ 4C^n_{2n-2}=\frac{4(2n-2)!}{n!(n-2)!}=\frac{4(2n)!(n)(n-1)}{(2n)(2n-1)(n!)^2}=\frac{2(2n)!(n-1)}{(2n-1)(n!)^2}$$
$$ 2^nC_n^n=2^n$$
So our original sum is equal to this:
$$C_{2n}^n\left( 1+1+\frac{2(n-1)}{(2n-1)}+\frac{2^2(n-1)(n-2)}{(2n-1)(2n-2)}+...+\frac{2^n}{C_{2n}^n} \right)$$
$$=C_{2n}^n\sum_{k=1}^n \frac{2^k(n-1)!(2n-k)!}{(n-k)!(2n-1)!}$$
$$=C_{2n}^n\sum_{k=1}^n \frac{2n}{n-1}=C_{2n}^n2n\sum_{k=1}^n\frac{1}{n-1}=C_{2n}^n \left( \frac{2n(n-1)}{n-1} \right) = 2nC_{2n}^n$$
So... how do I go from here? Also, I'm not sure if the last 2 steps are correct.
Edit: I was starting the sum at $k=0$, fixed it to $k=1$, and then changed  the rest after that.
Edit: I found the answer on a book, it's $2^{2n}$, so my answer is wrong... Still, I don't know what I did wrong, or how to correctly solve this.
 A: Let
\begin{align}
f(n)
&=\sum_{k=0}^n2^k\binom{2n-k}{n}\\
&=\sum_{h=0}^n2^{n-h}\frac{(n+h)!}{n!h!}
\end{align}
Then
\begin{align}
f(n+1)
&=\sum_{h=0}^{n+1}2^{n+1-h}\frac{(n+1+h)!}{(n+1)!h!}\\
&=\sum_{h=0}^{n+1}2\frac{n+1+h}{n+1}2^{n-h}\frac{(n+h)!}{n!h!}\\
&=2\sum_{h=0}^{n+1}2^{n-h}\frac{(n+h)!}{n!h!}+2\sum_{h=0}^{n+1}\frac{h}{n+1}2^{n-h}\frac{(n+h)!}{n!h!}\\
&=2f(n)+\frac{(2n+1)!}{n!(n+1)!}+2\sum_{h=1}^{n+1}2^{n-h}\frac{(n+h)!}{(n+1)!(h-1)!}\\
&=2f(n)+\frac{(2n+1)!}{n!(n+1)!}+\frac 12\sum_{h=1}^{n+1}2^{(n+1)-(h-1)}\frac{((n+1)+(h-1))!}{(n+1)!(h-1)!}\\
&=2f(n)+\frac{(2n+1)!}{n!(n+1)!}+\frac 12\sum_{u=0}^{n}2^{(n+1)-u}\frac{((n+1)+u)!}{(n+1)!u!}\\
&=2f(n)+\frac{(2n+1)!}{n!(n+1)!}+\frac 12f(n+1)-\frac 12\frac{(2n+2)!}{(n+1)!(n+1)!}\\
\end{align}
from which
\begin{align}
\frac 12f(n+1)
&=2f(n)+\frac{(2n+1)!}{n!(n+1)!}-\frac 12\frac{(2n+2)!}{(n+1)!(n+1)!}\\
&=2f(n)+\frac{(2n+1)!}{n!(n+1)!}\left(1-\frac 12\frac{2n+2}{n+1}\right)\\
&=2f(n)
\end{align}
from which $f(n+1)=4f(n)$, hence $f(n)=4^n$.
A: The number of binary numbers of length $2n$ whose $n+1^{th}$ 1 is in position $2n-k+1$ is ${2n-k\choose n}2^{k-1}$. Sum over $k$
A: The given sum is nothing but $$S_n=\sum_{k=0}^{n} {2n-k\choose n} 2^k= \sum_{k=0}^{n} \left [ {2n-k-1\choose n} 2^k + {2n-k-1\choose n-1} 2^k \right] $$
$$\implies S_n=\frac{1}{2}S_n-\frac{1}{2}  {2n \choose n}+ 2 S_{n-1}+\frac{1}{2} {2n \choose n} \implies S_n=4S_{n-1} \implies S_n =4^n$$
