Proving an Identity involving $4^N$

Question

I am trying to prove the following identity:

$$\sum_{k=0}^N\left({2 \, N - 2 \, k \choose N - k}{2 \, k \choose k}\right)=4^N$$

I have tried writing $4^N=2^{2N}=(1+1)^{2N}=(1+1)^N(1+1)^N$, and expanding each of these as a binomial expansion, but I have found nothing but dead ends so far. Any ideas?

I am currently working through a Ch. 3 "Generating Functions" from Analysis of Algorithms by Sedgewick/Flajolet. This is problem #30.

Thanks.

Answer 1

Let, $f(x)=\displaystyle\sum_{n=0}^{\infty}{2n \choose n}x^n=(1-4x)^{-1/2}$. Then your LHS will be coefficient of $x^N$ of $f^2(x)=(1-4x)^{-1}$ which is $4^N$=RHS.

Answer 2

Start off by noting $$ \sum_{k=0}^{N}\binom{2N-2k}{N-k}\binom{2k}{k}=[x^{N}]\left(\sum_{k=0}^{\infty}\binom{2k}{k}x^{k}\right)^2. $$ Now, what's inside the square is the OGF for the central binomial coefficients; you may have seen it before. It happens that $$ \sum_{k=0}^{\infty}\binom{2k}{k}x^k=\frac{1}{\sqrt{1-4x}}. $$ So, we find that $$ \sum_{k=0}^{N}\binom{2N-2k}{N-k}\binom{2k}{k}=[x^N]\frac{1}{1-4x}=[x^N]\sum_{k=0}^{\infty}(4x)^k=4^N, $$ as claimed.

Answer 3

Starting $$\tag 1\binom {n}{k}\binom{n-1/2}{k}=\binom{2n}{2k}\binom{2k}{k}/2^{2k}$$ In particular:

$$ \tag 2 \binom{-1/2}{k}=\bigg (\frac {-1}{4}\bigg) ^k\binom{2k}{k}$$

Now consider following Vandermonde's identity:

$$\sum\limits_{k}\binom{-1/2}{k}\binom{-1/2}{n-k}=\binom{-1}{n}=(-1)^n$$

Inserting $(2)$ and remove summing

$$\tag3 \binom{-1/2}{k}\binom{-1/2}{n-k}=\bigg (\frac {-1}{4}\bigg) ^k\binom{2k}{k}\bigg (\frac {-1}{4}\bigg) ^{n-k}\binom{2n-2k}{n-k}=\bigg (\frac {-1}{4}\bigg)^n\binom{2k}{k}\binom{2n-2k}{n-k}$$

Finally summing again:

$$\sum\limits_{k}\binom{2k}{k}\binom{2n-2k}{n-k}=4^n$$