Proving $4^n=\sum_{k=0}^n2^k\binom{2n-k}{n}$ $4^n = \sum\limits_{k=0}^{n}2^k\cdot{{2n - k} \choose n}$
I tried formal power series, but failed.
 A: A solution through Complex Analysis and the residue theorem.
$$\mathcal{S}(n)=\sum_{k=0}^{n} 2^k\binom{2n-k}{n} = \sum_{k=0}^{n}2^{n-k}\binom{n+k}{n} $$
is the coefficient of $x^n$ in the product between $\sum_{k\geq 0}2^k x^k=\frac{1}{1-2x}$ (geometric series) and $\sum_{k\geq 0}\binom{n+k}{n}x^k = \frac{1}{(1-x)^{n+1}}$ (stars and bars). In particular
$$ \mathcal{S}(n)=\text{Res}\left(\frac{1}{(1-2x)\left[x(1-x)\right]^{n+1}},x=0\right) $$
but due to the symmetry of the meromorphic function $\frac{1}{(1-2x)\left[x(1-x)\right]^{n+1}}$ the residue at $0$ and the residue at $1$ are the same number. The only other pole is at $x=\frac{1}{2}$ and the sum of the residues is zero, hence $\mathcal{S}(n)=4^n$ can be proved from the straightforward
$$ \text{Res}\left(\frac{1}{(1-2x)\left[x(1-x)\right]^{n+1}},x=\frac{1}{2}\right)=-2\cdot 4^n. $$
A: $$
\begin{align}
\sum_{k=0}^n2^k\binom{2n-k}{n}
&=\sum_{k=0}^n\sum_{j=0}^k\binom{k}{j}\binom{2n-k}{n}\tag1\\
&=\sum_{j=0}^n\sum_{k=j}^n\binom{k}{j}\binom{2n-k}{n}\tag2\\
&=\sum_{j=0}^n\binom{2n+1}{n+j+1}\tag3\\
&=\sum_{j=0}^n\binom{2n+1}{n-j}\tag4\\
&=\frac12\sum_{j=0}^{2n+1}\binom{2n+1}{j}\tag5\\
&=\frac12\cdot2^{2n+1}\tag6\\[12pt]
&=4^n\tag7
\end{align}
$$
Explanation:
$(1)$: use the binomial theorem to expand $(1+1)^n$
$(2)$: change order of summation
$(3)$: Vandermonde Identity
$(4)$: symmetry of Pascal's Triangle
$(5)$: average $(3)$ and $(4)$
$(6)$: use the binomial theorem to expand $(1+1)^{2n+1}$
$(7)$: simplify
Step $(3)$ is actually an extension of Vandermonde using negative binomial coefficients:
$$
\begin{align}
\sum_{k=j}^n\binom{k}{j}\binom{2n-k}{n}
&=\sum_{k=j}^n\binom{k}{k-j}\binom{2n-k}{n-k}\\
&=\sum_{k=j}^n(-1)^{k-j}\binom{-j-1}{k-j}(-1)^{n-k}\binom{-n-1}{n-k}\\
&=(-1)^{n-j}\binom{-n-j-2}{n-j}\\
&=\binom{2n+1}{n-j}\\
&=\binom{2n+1}{n+j+1}
\end{align}
$$
A: With formal power series as requested by OP we may write
$$\sum_{k=0}^n 2^k {2n-k\choose n}
= 2^n \sum_{k=0}^n 2^{-k} {n+k\choose n}
= 2^n \sum_{k=0}^n 2^{-k} [z^n] (1+z)^{n+k}
\\ = 2^n [z^n] (1+z)^n \sum_{k=0}^n 2^{-k} (1+z)^k
= 2^n [z^n] (1+z)^n \frac{1-(1+z)^{n+1}/2^{n+1}}{1-(1+z)/2}
\\ = 2^{n+1} [z^n] (1+z)^n \frac{1-(1+z)^{n+1}/2^{n+1}}{1-z}.$$
We get from the first piece
$$2^{n+1} [z^n] (1+z)^n \frac{1}{1-z} = 
2^{n+1} \sum_{k=0}^n {n\choose k} = 2^{2n+1}.$$
The second piece yields
$$- [z^n] (1+z)^{2n+1} \frac{1}{1-z}
= - \sum_{k=0}^n {2n+1\choose k}
= - \frac{1}{2} 2^{2n+1}.$$
Joining the two pieces we find
$$2^{2n+1} - 2^{2n} = 2^{2n} = 4^n.$$
A: Another (shorter) way to approach this is
$$ \bbox[lightyellow] {  
\eqalign{
  & \sum\limits_{0\, \le \,k\, \le \,n} {\left( \matrix{
  2n - k \cr 
  n \cr}  \right)2^{\,k} }  = \sum\limits_{0\, \le \,k\,\left( { \le \,n} \right)} {\left( \matrix{
  2n - k \cr 
  n - k \cr}  \right)2^{\,k} }  =   \cr 
  &  = \sum\limits_{0\, \le \,j\,} {\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( \matrix{
  2n - k \cr 
  n - k \cr}  \right)\left( \matrix{
  k \cr 
  k - j \cr}  \right)} }  = \sum\limits_{0\, \le \,j\,\left( { \le \,n} \right)\,} {\left( \matrix{
  2n + 1 \cr 
  n - j \cr}  \right)}  =   \cr 
  &  = {1 \over 2}\sum\limits_{l\,} {\left( \matrix{
  2n + 1 \cr 
  l \cr}  \right)}  = {{2^{2n + 1} } \over 2} \cr} 
}$$
where the bounds in brackets means that they are implicit in the binomial, and
where in the middle step the Double Convolution is used, which is
$$ \bbox[lightyellow] {  
\eqalign{
  & \sum\limits_{\left( {m\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( \matrix{
  a - k \cr 
  n - k \cr}  \right)\left( \matrix{
  k + b \cr 
  k - m \cr}  \right)}  = \sum\limits_{\left( {m\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{n - m} \left( \matrix{
  n - a - 1 \cr 
  n - k \cr}  \right)\left( \matrix{
   - m - b - 1 \cr 
  k - m \cr}  \right)}  =   \cr 
  &  = \left( { - 1} \right)^{n - m} \left( \matrix{
  n - m - a - b - 2 \cr 
  n - m \cr}  \right) = \left( \matrix{
  a + b + 1 \cr 
  n - m \cr}  \right)\quad \left| \matrix{
  \;a,b \in R \hfill \cr 
  \;n,m \in Z \hfill \cr}  \right. \cr} 
}$$
A: Try formal power series harder. The same Snake Oil Method I used to answer one of your other recent questions, works here as well. I will let you work through this one on your own with a few hints. Let $B=B(x)=\frac{1}{\sqrt{1-4x}}$ and $C=C(x)=\frac{1-\sqrt{1-4x}}{2x}$ be the generating functions for the central binomial coefficients and Catalan numbers, respectively. Then
$$
B=\frac{1}{1-2xC}, \qquad B^2=\frac{1}{1-4x},
$$
and
$$
\sum_{n=0}^{\infty}\binom{2n+k}{n}x^n=BC^k.
$$
The last inequality can be proved combinatorially: consider all lattice paths from $(0,0)$ to $(2n,k)$ using steps $u=(1,1)$ and $d=(1,-1)$. Then any such path can be written uniquely as $P_0uD_1uD_2u\dots uD_k$, where $P_0$ is a grand Dyck path and $D_1,\dots,D_k$ are Dyck paths, all together (with $P_0$) of total semilength $n$.
