Solving $\sum_{k=0}^n 2^k \binom{2n-k}{n}=4^n$ using generating functions

Question

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.

Answer 1

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*}