Solving $\sum_{k=0}^n 2^k \binom{2n-k}{n}=4^n$ using generating functions So I have to show this identity. $$\sum_{k=0}^n 2^k \binom{2n-k}{n}=4^n$$
I tried two techniques to do it. First one would be seeing that it's convolution of two sequences: $\langle 2^n \rangle _{n=0}^\infty$ and $\langle \binom{2n}{n} \rangle _{n=0}^\infty$
That gives me:
$$\lbrack \sum_{n=0}^\infty 2^n x^n \rbrack \times \lbrack \sum_{n=0}^\infty \binom{2n}{n} x^n \rbrack =$$
$$\frac{1}{1-2x} \  \frac{1}{\sqrt{1-4x}} =$$
$$\sum_{n=0}^\infty x^n \sum_{k=0}^n 2^k \binom{2n-k}{n-k}$$
So now we need to show that
$$\lbrack x^n \rbrack \frac{1}{1-2x} \frac{1}{\sqrt{1-4x}} = \frac{1}{1-4x}$$ But i'm unable to do it.
Second method would be snake oil method:
$$\sum_{n=0}^\infty x^n \sum_{k=0}^n 2^k \binom{2n-k}{n} =$$
$$\sum_{k=0}^\infty 2^k \sum_{n=k}^\infty x^n \binom{2n-k}{n} = \text{where l := n - k}$$
$$\sum_{k=0}^\infty 2^k x^k \sum_{l=0}^\infty x^l \binom{2l + k}{l+k} $$
But i'm stuck here too.
I mean i know that
$$\sum_{n=0}^\infty \binom{2n}{n} x^n = \frac{1}{\sqrt{1-4x}}$$
And if i multiply it by $x^k$ i get
$$\sum_{n=0}^\infty \binom{2n+2k}{n+k} x^{n+k} = \frac{x^k}{\sqrt{1-4x}}$$
And it's almost what i need to calculate... but yeah, almost.
I will really appreciate some help on this.
 A: Here is a variation based upon the coefficient of method. We use the symbol $[z^n]$ to denote the coefficient of $z^p$ in a series. This way we can write e.g.
\begin{align*}
  [z^p](1+z)^q=\binom{q}{p}\tag{1}
  \end{align*}

We obtain
\begin{align*}
\color{blue}{\sum_{k=0}^n\binom{2n-k}{n}2^k}&=\sum_{k=0}^{n}[z^n](1+z)^{2n-k}2^k\tag{2}\\
&=[z^n](1+z)^{2n}\sum_{k=0}^n\left(\frac{2}{1+z}\right)^k\tag{3}\\
&=[z^n](1+z)^{2n}\frac{1-\left(\frac{2}{1+z}\right)^{n+1}}{1-\frac{2}{1+z}}\tag{4}\\
&=[z^n]\frac{(1+z)^{2n+1}-2^{n+1}(1+z)^n}{z-1}\\
&=[z^n]\frac{1}{z}\sum_{j=0}^\infty z^{-j}\left((1+z)^{2n+1}-2^{n+1}(1+z)^n\right)\tag{5}\\
&=\sum_{j=0}^n[z^{n+1+j}](1+z)^{2n+1}\tag{6}\\
&=\sum_{j=0}^n\binom{2n+1}{n+1+j}\tag{7}\\
&=\sum_{j=0}^n\binom{2n+1}{j}\tag{8}\\
&=\frac{1}{2}2^{2n+1}\\
&\,\,\color{blue}{=4^n}
\end{align*}
and the claim follows.

Comment:

*

*In (2) we apply the coefficient of operator according to (1).


*In (3) we do some rearrangements and use the linearity of the coefficient of operator.


*In (4) and (5) we use the geometric series expansion.


*In (6) we use the rule $[z^{p+q}]A(z)=[z^p]z^{-q}A(z)$ and restrict the upper limit of the sum with $n$ since the exponent $n+1+j\leq2n+1$. The second binomial $(1+z)^n$ does not contribute to $[z^{n+1+j}]$ and can be skipped.


*In (7) we select the coefficient of $z^{n-j}$.


*In (8) we replace $j$ with $n-j$ and apply the binomial identity $\binom{p}{q}=\binom{p}{q-p}$.
Hint: The Cauchy product in your approach is slightly different, since
\begin{align*}
\left(\sum_{n=0}^\infty 2^nx^n\right)\left(\sum_{n=0}^\infty\binom{2n}{n}x^n\right)
=\sum_{n=0}^\infty\left(\sum_{k=0}^n2^k\binom{2n\color{blue}{-2k}}{n-k}\right)x^n
\end{align*}
